To find Elekong, go to Ita and head for the desert to your right. Go two screens to the right then go to the bottom of the area, but do not go in the stairs. Once your reach the bottom, go to the left then go back to the right. Keep repeating this until you see a lake with two palm trees. Enter it and go down the stairs. Talk to him and he will join you.