You are just really, really unlucky with the RNR system. I got Garuda's my second run and Ifrit's on my 30th. Garuda's isn't necessary to progress to Titan. Just make sure you have around 3150-3200 HP for Titan which you have well over. Garuda's weapon is only useful for Titan because you get your relic soon after. So don't sweat it and move on!