You don't need cats until longbowmen come out, prats are perfectly capable of taking out archers, axemen, and spearmen in cities and winning in equal numbers. And the macemen are hardly slightly later, it requires code of laws which costs one and a half times as much to research as ironworking, and itself costs more than twice the cost of the entire iron working line.
You can easilly get iron working by 2000 bc, you'll be lucky to get civilservice by 500 AD unless you completely neglect everything else and straight shot for it.
Against each other axemen are slightly worse than praets, against anything else in the game you're going to need two axemen to do the damage of one preat.
I think a much more fair value for the praetorian would be 6 str but 25% attack bonus to archer and 10% to raiding cities or something of the like. It would be as good at it is now at city assaults but there would actually be suitible counters such as axemen or war elephants whereas now there simply is no counter, Praets just win vs everything, nothing else stands a chance until macemen, xbows, and knights.