I've heard several theories on how to increase Agility; however, it still seems rather random to me.
I heard you're supposed to fail at running and then end the battle, and this sounds credible as it fits with the level techniques in this game (which basically are = "fail/mess up in order to improve").
I've also got a personal theory that Agility will improve if you wear Agility-increasing equipment for a while, e.g. the Goldpin and the Thief Glove.
I'm not sure, though; do you know anything?