Two Things

[Metathron]

Which difficulty did you play in KB:TL?

If easy or normal, you shouldn't have suffered such great losses so as to be chronically running out troops, and my advice would be to read some threads on these boards that discuss game strategies/tactics. Or ask questions of your own, perhaps describe a battle of yours in details and others will tell you what you are doing wrong.

If hard or impossible, why be shocked at meeting overpowering troops in a new area? It's not like you have to fight everything that crosses your path. You have to pick your battles: grab free leadership banners and treasure chests, analyze an enemy army before you attack them, i.e. is your army composition suitable for fighting your enemy's army, etc.