After Melchior tells you about an ancient rock that could be used to repair the Masamune, you should go to the past.
Go to the Past
If you have not already done so, use a Gate to return to the End of Time, then use the southwest pillar of light to go to Mystic Mountain, 65,000,000 B.C.
Defeat the Reptites. Then meet a new character (default: Ayla). Follow her to the next area.
Open the chest on the way (Berserker). Use Lightning on the dinosaurs to weaken them, then use regular attacks.
Go south to exit the area, then go east and enter the huts. In one, a woman will give you "sweet water" which replenishes your HP/MP.
Go north to the Chief's Hut and talk to Ayla.
At the party, talk to your friends and Ayla a few times, and eventually the soup-eating contest begins. Press the A button repeatedly to quickly drink the soup.
In the morning, wake up Ayla. Decide which party member to bring with you, then go outside. You can talk to the kid in the southwest hut to find out where the Reptites went: the Forest Maze.