It's in an island just east of Bafsk. From Altea, sail to the east until you come across a narrow peninsula. Go through the peninsula, and then go southeast until you come across the island. You can keep checking the map to see where Bafsk and the island next to it are, and try to find it that way.