Попробуйте следующее:
import random a = dict(....) # a is some dictionary random_key = random.sample(a, 1)[0]
Это определенно работает.