Damage dealing insane party:
Steiner: Shock
Freya: maxed Dragon Crest
Quina: maxed Frog Drop
Zidane: maxed Thievery

With auto-potion, auto-regen and shadow absorbing armor on each of them, it'll be hard to lose.

If all else fails, go find all the friendly animals and give them the ores they want, until you get to the Golden Yan. Give him a diamond and he'll make a reference to Ozma. I think Ozma will be slightly slower and weaker if you do this.