Leave Sei'an City and go to the northwest corner of Ryoshima Coast. You will find a pair of guards blocking access from the northern coastal area, though they will let you pass with the border key that Himiko gave you. With their permission, head north to continue your quest.
As soon as you enter North Ryoshima Coast, you will run into a new enemy, the Earth Nose. To defeat the enemy, use the Veil of Mist brush technique to slow time, then move in with a flurry of attacks to quickly take it out. You can now explore the area of the North Ryoshima Coast. Check out the eastern section of the land along the beach to find Urashima buried in the sand. Give him a headbutt to wake him up and he will tell you of a mysterious Orca that can bring those who are worthy to the Dragon Palace. When you are ready, go to the dock that Urashima was talking about, along the coast to the north-east. Stand at the end of the dock at night and wait for daylight to come. As it does, Orca will appear and speak with Amaterasu and Issun, offering to bring the two to the Dragon Palace after you have completed a challenge.Controlling Orca, you can swim around the ocean's waters without fear of being sucked up by the Water Dragon. Make your way to the island to the northeast and hop off Orca. At the top of the hill you'll find the entrance to Catcall Tower.