wow. yesterday i was in the exact same shoes as u were in.but my stats were a lil higher. cloud (the strongest in my party) was around lvl 33. and like u, demon gate (?) mopped the floor with me.

so i went outside, and lvld up outside the temple. there shud be lil red things taht comes in groups of 3, 4, and 5. they give the most experience. i spent an hour or two leveling up to level 40, and also went to gongaga and rocket town to obtain the "time" and "barrier" materia, because i didnt' have them.

i went back inside to the temple of the ancients, and after beating red dragon, equiped the bahamut materia to aeris. also, make sure she has the cure-all combo. caste barrier and haste, and that shud allow ur characters to defeat him. when i fought, vincent also had the death gigas limit break, and that "gigadunk" really helped out, and did 1000+ each turn. after that, the rest is easy. shudn't take too long, or that much effort. good luck, and i hope i helped