The Sunken Gelnika is located here (underwater, use the submarine):
Save. Save often. Grab the chest in the hallway to receive Heaven’s Cloud. Go through the door on the north wall and grab the Megalixir on the upper catwalk, the Escort Guard in the other chest in the corner, and one of the best Materia in the game, Double Cut, on the bottom floor. There’s also a chest on the top left of the bottom floor that contains the Conformer, Yuffie’s ultimate weapon.
Head back to the save point and then head through the door on the left. In here you’re going to fight Rude and Reno one last time.
Turks (Rude and Reno)
Both Reno and Rude have items on them that you should try your hardest to steal – Ziedrich and Touph Ring. They’re incredibly rare, and you won’t get another chance. Reno will use a move that confuses your teammates, so equip Ribbons if you have them. Compared to some of the random encounters down here these guys are nothing.
HP: 15,000 (Rude) + 20,000 (Reno)
Go through the doorway behind where Reno and Rude where standing. The first chest up ahead contains a Megalixir. Follow the catwalk all the way around to another chest which contain Spirit Lance. Travel to the lower floor and grab the red Hades Materia sitting on the ground by the wreckage. Hades is an awesome materia to pair with Added Effect. There are two more chests on the lower floor containing Highwind and Outsider.
All done with the Sunken Gelnika.