If you haven't done the Rhinostery series of quests (completed "Blue Ribbon Blues" by killing Lich C Magnus, and at least started/opened "Toraimarai Tormoil"), then the only entrance you will have availble to you is via Horotuo Ruins (the East tower in East Sarutabaruta).
The path via the ruins leads you to the three mage gate, which you can open by having a RDM, BLM, and WHM each standing on the corresponding platforms (thus the name of the gate), OR you can have someone with a Portal Charm open it for you. You get the Portal charm by trading a rolanberry (not a pie, just the fruit) to Kupipi in Heaven's Tower after you have completed Windurst mission 3-2 (which means you must be a Windy citizen, or at least used to be). Note that this door CANNOT be opened from the inside, unfortunately. It is a one way door.
I've found that the Scavenger Crabs and Stygian Pugils drop the keys fairly often (I got one fast by just playing around w/ NPC and staff skillup). One really good camp is I-8/J-9 of the second map, which is a very short distance from the Windurst Walls zone. The other good camp would be F-9/G-10. Everything agros, so be careful.