I never really used Red Mages after the first few dungeons. I think I simply changed my Red Mage to a Black Mage around the time you visit the Nepto Shrine. If you really want a replacement for your Red Mage, I think Dark Knight is the closest I could think of since that class can both attack and use magic.