You should have a Ribbon already from Locke's scenario waaaaay back during the WoB. It's in the hidden room in the underground passageway, where Locke rescues Celes. It's still there in the WoR, so stop what you're doing, go back to South Figaro and get that Ribbon. There's also another hidden room off of the hallway where Locke first sees Celes that has a Hyper Wrist and Running Shoes, if you haven't already gotten them.

But really, Ribbons aren't important. You don't need four Ribbons equipped on everyone at all times, and there are plenty of better relics to use. I would focus on getting the really good relics, and not worry about Ribbons so much.

And the bird enemy in Phoenix Cave(Aquila) does not have Ribbons to steal. It has an Economizer to steal as a rare steal, but the enemy itself is rare as well, and you're better off getting both Ribbons(steal) and Economizers(win) off of Brachiosaurs in the Dragon Forest. You'll be spending plenty of time levelling there anyways, so you'll have all the Ribbons you can stomach.