Select random element from "non uniform" python dictionary

I have a python dictionary in which values are lists of integers:

key1 -> [1, 2, 3]
key2 -> [1, 2, 3, ... 17]
key3 -> [1, 2, 3, 4, 5]

I want to select a random tuple(key, val) where val is a random value from the list of values (for example: key2, 8). The random selection must be uniform across all the values, so for example, this method is not uniform:

random_key = random.choice(d.keys())
random_val = random.choice(d[random_key])

because the lists are not of the same length. I know the length of the concatenation of the lists, n, so my current approach is the following:

idx = np.random.randint(n)
c = 0
found = False

for k in D:
    for v in D[k]:
        if c == idx:
            found = True
            do_something_with_val(k, v);
            break
        c += 1
    if found:
        break

My question is: is there a better/faster method of doing this?