I'm not a Ninja, but I'm guessing your choice of element probably doesn't matter a whole lot.
I'm hoping you know this already, but Elemental Magic Skill (like what's found on Ice/Aquilo's Staff) does not affect Magic Accuracy or damage of Ninjutsu spells. The hidden effect on elemental staves (MAB and Magic Accuracy) would apply to Ninjutsu spells, but that's available on all the level 51 elemental staves, not just Ice/Aquilo's.
One advantage of using Hyoton is that many enemy classes are weak to ice magic (yagudos, tonberries, crabs, pugils, mandragora, gnoles, monkeys, turtles, bugards, lizards, peiste, wivres, bees, beetles, damselflies, scorpions, ladybugs, spiders, traps, cactus, kraken, slugs, birds, ***, rocs, colibri, puks, gears).
The downside of Hyoton is that many enemy classes heavily resist ice magic, including almost all types of undead, plus gigas and several others.
I'd say Katon is a good choice. Not many enemy classes are resistant to fire damage.
Ultimately, your choice!