It is almost 20 years since Bill Clinton, then America's president, spoke of a new breed of African leaders.
The five men he picked out - Ethiopia's Meles Zenawi, Rwanda's Paul Kagame, Eritrea's Isaias Afwerki, DR Congo's Laurent Kabila and our own Yoweri Museveni had a lot in common.
They were young, intelligent, had fought their way to power and promised a new pan-African order of strong, stable and efficient states. Compared to the likes of Jean-Bédel Bokassa, who had cannibalised his Central African Republic, or Mobutu Sese Seko, who had plundered Zaire, they were a breath of fresh air.
The end of the Cold War had left many of Africa's political crocodiles surplus to geostrategic requirements and driven many out of business. The continent was ready for reform - primarily liberalisation to open up its markets, and liberal democracy to open up its politics.
The optimism wasn't entirely misplaced. Disregarding the devastating Congo War, of which Clinton was curiously silent, and which was resuming just as he spoke, the turn of the millennium saw the end of many intractable conflicts on the continent that had been fuelled by external supporters.
In the first five years of the new millennium, long-running civil wars came to an end in Algeria, Sudan, Uganda, Sierra Leone, Liberia, Angola, Burundi as well as between Eritrea and Ethiopia. Even adjusting for subsequent lapses in Sudan, South Sudan, Ivory Coast, Chad and the Arab Spring, the continent is more peaceful today than it was 20 years ago.
Yet in many of these countries, the end of civil war has not necessarily led to peace but has been replaced, instead, by political violence of varying degrees and formations, from asymmetric terrorism from non-State actors in Nigeria and Somalia, to ethnic- and linguistic-fuelled conflagrations in Kenya, Uganda, Cameroon, Ethiopia and elsewhere. The promise of Western-style electoral democracy as a panacea to the continent's governance question has done okay in a few countries in west and southern Africa, but fallen severely short elsewhere.
Liberation movements that came to power by the gun, from Ethiopia to Angola via Uganda, Rwanda and Mozambique have found it relatively easy to bend or remove the legal restrictions that would require them to detach their political wings from State institutions or bring about enforced change in leadership.
In a few extreme cases, such as Eritrea and DR Congo, the leaders have simply not bothered with holding elections.
There is a lot of literature on why many liberation movements tend to be autocratic and incompetent in government (clue: The very things that make them good at war are what make them poor at governing), but it is worth reminding ourselves that the African state, as a colonial construct, is a work in progress. In some cases (think Somalia or South Sudan) it is unable to monopolise legitimate violence within its borders or defend its territorial integrity.
Those that do often discover they lack organic institutions or political cultures to control the exercise of power and respect for rules and fall back on the protection of tribe and family. Electoral democracy therefore becomes ritualistic, with perfunctory elections and institutions used to provide procedural accountability (often to outside donors) and a veneer of legitimacy. The governed need not give consent; they only need to witness the rituals.
So, what did we fight for? A quick examination shows that while Africa saw very many civil wars over the last 50 years, there were hardly any wars of conquest. Yes, there were wars of secession in Katanga, Biafra and elsewhere, and wars to eject the colonialists and the apartheid regime in southern Africa, but we did not have many serious wars to undo the colonial borderlines, grab territory or recreate the pre-colonial nation states.
Post-independence leaders took a pragmatic decision to maintain colonial borders, partly out of self-interest; they were in power and had no incentive to trade power or territory with neighours or traditional kingdoms.
What if, however, they had created a useful crisis by taking the damn thing apart then put it back together, one nation-state at a time, in negotiated settlements over history, identity, political culture, consent and collective self-interest in a world that had clearly changed significantly?
Not doing so merely postponed the crisis. It meant that we have spent half a century trying to transpose political systems onto shaky foundations and institutions deliberately designed to repress the natives, and ended up with small, unviable, poorly-governed chiefdoms pretending to be nations.
Did we waste our wars fighting over diamonds, as proxies, or for our tribe's turn to eat instead of fighting over a new African order? We've had too many men with guns, but not enough gunmen with plans.
Mr Kalinaki is a journalist and a poor man's freedom fighter.