Reports said that under new arrest warrants, an extradition request had already been sent to South African authorities.
Kayumba, the former Chief of Staff of the Rwandan army before being appointed as Ambassador to India, fled the country immediately after the attacks in late 2010.
He passed through Uganda and proceeded to South Africa where he is currently seeking asylum, it said.
The moves comes a few weeks after a new report by the UN Group of Experts on the Democratic Republic of Congo has indicated that the Rwandan fugitive former senior officer who lives in South Africa, is the leader of a new rebel group known as “P5”, which operates in DR Congo’s South Kivu province.
P5, the UN Group of Experts report says, is a coalition of Rwandan “opposition political organisations”, including the Amahoro People’s Congress (AMAHORO-PC), the Forces démocratiques unifées-Inkingi (FDU INKINGI), the People’s Defence Pact-Imanzi (PDP-IMANZI), the Social Party-Imberakuri (PS IMBERAKURI) and the Rwanda National Congress (RNC).
The UN Group of Experts report indicates that P5 mostly received its arms and ammunition from Burundi and recruits fighters from across the region.
The findings were based on separate interviews conducted by the Group with different ex-combatants, all of whom told the Group that another person called Shaka Nyamusaraba was the commander of the armed group, which included both foreign combatants, most of Rwandan origin, and Congolese Banyamulenge.