According to the drop tables in single-player (data\global\excel\TreasureClassEx.txt):
The Countess has a 1/68 chance for a Key of Terror on each item drop in a 1-player game with a total of 5 drops. This works out to at least 1 key per ~14 runs.
The Summoner has a 1/56 chance for a Key of Hate on each item drop with a total of 5 drops, giving at least one key every 11-12 runs.
Nihlathak has a 1/61 chance for a Key of Destruction on each of his 5 drops, working out to at least 1 key per 12-13 runs.
If you run them in 8-player games, your chances of finding keys increases slightly.
Your mileage may vary, though, especially if Blizzard changed the drop rates on the realms.