Ultima is kinda difficult to beat, specially in the conditions in which you battle him. What happens in SoR is that characters need a lot of time to level up, specially right after getting to the only town in the world. If you choose to battle the Weapon (and remember this for when you play the game), make sure you get the Flare tomes as I posted previously, for it is basicaly your only way to inflict significant damage to him. Also, talk to the orbs which improve your characters' stats before talking to the central orb, where Ultima awaits (Hope you can remenber all this and that this is no spoiler for anybody).