Nile Valley is where they have stayed for a very long time.
There is really no such thing as a definite geographic Urheimat for Ancestral East Africa because that lineage is supposedly tied to one of the oldest lineages we have. When we go back to 100 kya, I can't really say where people were exactly but we can say, that those people split from West Africans ~80 kya, and that they split from Eurasians ~70 kya, and so on. It's kind of strange how East Africans were the same trunk as non-Africans when they split from West Africans. It's fascinating.
ANA was probably a population that split from the lineage that was West African-East African-Eurasian, so maybe some 10s of thousands of years before we split from West Africans because I remember the Taforalt paper claimed the African DNA at the exclusion of the Near Eastern stuff was equidistant to the West Africans and East Africans. That to me is telling how it was just another deep African variation that went north and started to diverge. Why do I say that? Because Ust'Ishim, a lineage that split from Eurasians before the West and East Eurasian split was equally distant to both Eastern Eurasians and Western Eurasians. So ANA has to be some diverged group that split from us before we split from West Africans. It can also be a good reason why it shows strange Eurasian-like properties because maybe it enriched some variation of the African-sourced Eurasian-like diversity it had when going through the genetic drift (because this was, after all, a time when we were one diversity with non-Africans) -- remember that non-Africans are just a bottlenecked version of an African variation, after all.
But given ANA is in North Africa, Ancestral East African rich people are in Northeast Africa and West Africans are in the northern part of West Africa (just to give this consistent meaning), then I think the genesis could be anywhere in the modern Sahara, maybe central, maybe even eastern. The Saharan desert was a very different place back then with likely diverse forms of environmental variation. I don't think the group separated in southern Africa or anything like that.