Agreed, there doesn't seem to be a fast way, but there seem to be a few options you have in-game to help with the process. There's training your chocobo, certain food that buffs experience points gained, and the FC buff. I think those people you're seeing with high level chocobos have probably devoted quite a bit of time on it.