A lot of people have had trouble with this part of the King's Quest and the map... so I can tell you what I know of and remember, and hope it helps. Some other players should be on here shortly, and may be able to help you further too.
The Dusty Ruins is the square at the very top right next to Twiggy Lake, and it's accessed from The Ancient Courtyard, which is the unmarked square right under it. I'm pretty sure that the 3 keys you're after come from The Dusty Ruins, The Gritty Dunes and The Secret Alley. You also need to finish the puzzles in these zones to actually get these keys, even though the puzzles are Monsters when completed, not keys, you'll get the keys too when you capture the Monsters. First thing you should do is to click on The King's Quest Icon on your map under your Level and Power Bars. This should give you the information on what you're needing to do and where. Sometimes you have to do other things before it lets you do certain Quests that you're trying to, even though it shows them as being available, there are times that things show up before you can actually do them. So, if you haven't completed the puzzles in these 3 zones, you'll be needing to get those finished up.
Good luck.