They likely had some of these types of ships (not necessarily the same classes but older equivalents) when it was just the Prophets and Elites. They may have built up their fleet when they encountered the Brutes, Grunts, Hunters, Drones, etc. The major sentient beings the growing Covenant encountered would bolster the hegemony as each species was conquered. Humans are just the last in a long line of encounters, and one the Covenant had a tough time against. Recall the Elites talking in the Conversations from the Universe booklet: they wondered why the humans were not offered admission into the Covenant as the other species had been.