You get rusted keys from chests in maps, which can be analyzed by Natalie in Tria near the top-left. To analyze a key,
just talk to her and pay the fee and you will be rewarded with either a B1 key or a B4 key. These keys can then be used
to enter the Treasure Dungeon and get rewards.
The cost to analyze these keys is reset per day, starting at 100,000 Mesos, going up to 300,000 Mesos, 500,000 Mesos, and so forth.
To farm Rusted Keys, I found that you can farm Wooden and Golden Chests in North Royal Road at XX:15-XX:20 and XX:55-XX:00. Wooden chests spawn at those times, and golden chests respawn every 20 minutes.