They're both right over on the other side of the map: I'm guessing it'll take you a while to get to that point. Braccus' tomb has a nice maze in front of it, you can't miss it (well okay, you could miss it if you're anything like me) and the shrine tended by Gratiana is fairly nearby on the south coast. Watch out for scratchy void creatures.