Leo didn't outrank him. It's explicitly stated that Kefka, Leo, and Celes were all generals. It's just that everyone liked Leo a better because, well, the obvious issue of personality.

It's also demonstrated that Kefka didn't just recently climb the ranks in that Ghastla tells Celes and him that it's their "birthright" to rule the world. Thus, the Emperor must have been endeared by him for quite a while.