Once you've unlocked access to the Challenge Log, you're guaranteed a chocobo level every 7 weeks if you kill just 100 mobs per week with your companion out, because the Companions category gives 5% and 10% for the two challenges (total 15%). This is just with a quite easy bare minimum effort of 100 kills per week.
PS, the cap is 20. Once you hit 10, you can feed your chocobo a Thavnairian Onion to raise its cap to 11. Once you hit 11, you can feed your chocobo a Thavnairian Onion to raise its cap to 12. Once you hit .... (simile) ... to 20.