Regirock is in the Desert, just go into the desert, and go south... should be easy to find.
Registeel on route 120, just left of Lilycove. Just fly to Lilycove, go left, there is a Ladder/Stairs leading up, go through the thick grass, and there is the entrance. By the person who gives you a berry.
Regice is on route 105, the one you orginally have Briney take you through on the boat. It is North of Dewford, to the left in a small group of islands.
I may have Rock and Steel confused, but the location of the caves are correct, even if the Pokemon in them are not.
Advice on catching them easier. Get a high level, fast Pokemon with Endevor. Let it get Poisoned/battle til it has 1 HP, then heal the Poison. Take it to face Regi's, then use something else to sleep/paralyze it. 1HP plus status will increase you rodds of catching greatly.
Endevor with 1 HP. Endevor takes your opponents HP, and subtracts your HP. So if they have 200HP, and you have 1, it does 200-1=199 damage, leaving it with 1HP. Its like a 1 hit False Swipe.