There are private academies (Blackjack School of Combat springs to mind), so "Academy" doesn't necessarily have to be government sponsored. And even if they went to a government academy, maybe they mustered out at some point (i.e., their "Tour of Duty" or even "Covert Ops" modules could have happened before they turned mercenary). As for coming from that affiliation, your citizenship doesn't necessarily have to match your affiliation (unless your Capellan, or maybe Kuritan).