Right, Africa, that's the one with Scipio against Hannibal, part I. And I believe Zama is next. Well, that's never going to be an easy battle, but it shouldn't be stopping you cold like that.
I can offer you the advice that has worked for many inquiries of this sort...
There is a thing called the Possum Method. It's not perfect, and it's not the only path to success, but it does work.
INFANTRY
Take Swordsman, Drill, and Feint for your first three skill levels.
Then go Advanced Swordsman, Disciplined Formations, Advanced Drill, Advanced Feint. If training Legionnaires, etc, that start with Disciplined Formations, then just ignore that step; you can grab Armor Penetration or Missile Protection instead. But we'll assume that we're talking about Auxilia or something that needs it. Now you're level 8.
Next take the same three skills, Swordsman, Drill, Feint at the Expert level. Now you are level 11.
At level 12, take Master Swordsman.
At level 13, take Frenzy if available; some troop types get it, and some don't. Otherwise, start on Missile Protection and Armor Penetration. OR look at the
Special Equipment thread, decide on something you want, and start driving on the requirements for that.
Be aware that you must have Master Feint in order to qualify for Weapons 4 and Weapons 5.
CAVALRY
All the same as above, except that instead of interrupting the sequence at level 6 for Disciplined Formations, you interrupt it at level 8 to take Trample. Cavalry in general can also, if you wish, interrupt the sequence once or even twice more to take Advanced or even Expert Trample. But do not not not neglect Drill with your cavalry units. You will inevitably wind up using them as a Fire Brigade, and they have to be able to
MOVE when you need them to move!
The "Protection From XXX" skills are a waste of time.
The "Anti-XXX Specialist" skills are a waste of time,
including Anti-Elephant.
Dodge and Parry are a waste of time.
Endurance is not a total waste, but I am still not a big fan because the HP it adds at any given level are only a small percentage of the HP you would already have
at that level.
Do not neglect equipment entirely in the early game. Even just Weapons 1 can help enormously. But of course it's a balance between recruiting troops early enough to get them experience enough to meet the challenges of the mid-to-late game, and having good enough equipment to get that far at all.
As I said above, this method is not perfect, nor is it the only path to victory. But it does work. I have been advocating this approach for about 2 years now. I have offered it as suggestion to more "help me I'm stuck on this battle" threads than I can count, and every one who has tried it has come back and said that it worked.
Of course, this means starting over again...
Because, you see, decent Heavy Cavalry should eat Skirmishers like a seagull gobbling french fries in the parking lot at McDonalds
Oh yes, and two final caveats.
1) While the Possum Method consistently yields very good to excellent results in the regular game, at difficulty levels up to Hard, there are a certain modifications to the Possum Method which have been suggested by those who regularly play the game at the Very Hard setting.
2) Cult of Mithras, the Legion Arena expansion which continues the Roman Campaign into the Afterlife, introduces new "supernatural" troop types (ghosts and ghouls and such). The Possum Method has not shown itself to be particularly successful against these "supernatural" troop types.
In my country this is the synonym for «auger» or «gimlet».