I think the future of the Legion really comes down to how close the vaults are in that region.
If you go into NE Colorado, Wyoming, South Dakota, you are into the ICBM fields. In the event of nuclear war, that region would be a radiated hell hole. I don't think anything would come out of that. These are also sparsely populated areas. Sure, they might have made vaults out there- lots of cheap real estate, but they are probably too far spread out.
Lets leave the Romans out and think about the American Indians, a decent model here given that Caesar forms the Legion out of assorted tribals, most of who are probably a few generators removed from the vaults.
While the American Indians were probably the world's best light cavalry in the middle of the 19th century, they had only enjoyed horses for about 100 years before. But even so, they never had the discipline and organization to be a significant challenge to US western migration. With few exceptions, the Indian Wars were pretty simple pacification campaigns fought by the US Army to make the routes west safe.
In the modern age, there are no horses and little in the of transportation. Communications are limited at best. While Caesar has an ideology, its all about war and war-fighting ideologies eventually exhaust themselves. Given great distances and sparse populations, it will be hard to keep these communities together. Without much transportation, these folks are kind of stranded and alone.
I doubt that the Legion would last much longer. Exhausted from war, chances are these folks are going to break apart into scattered and fairly autonomous communities- very much like the American Indians before they got horses.