They are connected mostly with the Agaw.
PS. Beja is more or less a dead language. It is not going to survive the 21st century. All the young Bejas are language shifting to Sudanese Arabic.
If afar/Saho can survive, so can Beja. Toe the language in most danger of dying out is Agew.