What if you store a large number of keys on the module right from the start, and get all the new keys from that list. That way the key switch message only needs to contain the index of the new key. Even better, store a huge random seed and generate all subsequent keys from that. Then you can also change key size and algorithm as needed without ever having to meet your contact in person again.