Or just keep a chocobo handy, which you have access to rather early in the game.