I understand everything boonet said about having to process much more visuals, therefore slowing down the FPS.
My suggestion is that the Klyros use their flying skill to transport themselves from place to place, but without you, the player, actually doing the flying.
You would go to your skills menu, select fly, then select the place you would like to fly to. You would only be able to fly to cities and other major locations. And only to places that you have been to before.
You would then see a short, generic, clip of a klyros flying, then you would be there, out the front of the city or major location.
The purpose of only being able to fly to places you have been before, is so that you cannot just fly round the whole world in your first hour of play. When going to a place for the first time, you would have do it on foot, the hard way.
Also, for flying characters, there should be a bar, like a mana or HP bar, that regenerates extremely slowly. This would make it possible to only fly like once a day.