I usually run a Fighter with a Red, White and Black Mage, but the Black Mage can be subbed for either another Red Mage or a Black Belt with no issues.  However, every party will be good, some just take longer to get strong enough to beat the game.  As for what to do, it's been a while, but I believe you have to kill Astos (the Dark Elf) to continue.  To fight him you need to collect the crown from the Marsh Cave.  There might be another thing you need to do as well, but the last thing on the to-do list is to return to Matoya's Cave, so you can just keep that part of the quest in the back of your mind.

Youtube

It is no fun playing the game with faqs. I only go to them after
dealing with something for three days.