Mage Notingale:
First of all, you must acquire either an Aurabird or an Airship in order to fight against the enemies who populate our skies. Since the number of Airships is limited, I recommend you acquire an Aurabird.
To do so, go meet Engineer Lekon and do what he tells you. Even if you decide to acquire an Airship, Lekon is worth talking to.
Check your map and I will tell you his location.