If you aren't sure on how to get to Ultima, I suggest using a Great Crystal map and following your way through using that. The mini map doesn't work, however you can check the name of which section you are in by viewing your main map.
There is a save crystal directly south of Ultima's room.
She cycles through several scenarios. Starting with (in chronological order): health sapping, mp sapping, no attacks, no magicks, no techniks, no items, slow charge time.
She also uses redemption between her normal attacks, which can inflict sap.
Her main move is Holyja, which inflicts reverse, and she will use renew in order to put you at 1 HP.
She'll use Holyja every 12 attacks, then at 80%, and more frequently after 70%.
She is weak against blind and dark, so cast blind to cause her to use Blindna on herself, giving you time to breathe.
Have ether's, Charge technic or siphon to restore your MP.
Esuna will remove Reverse.
Having the white mask from Necrohol and Sage's rings which both absorb Holy elemental damage will keep you fully healed when she uses Holyja.
The Yagyu Darkblade can also be found in the great crystal, along with black robes from Necrohol of Nabudis + bravery and berserk will do a lot of damage, and Darkga spell casters.
Good luck, and don't forget to grab the excalibur! (white robes + Exc on Knight/Bushi Basch is OP)