My suggestion is as follows
I have recreated my key (e.g. I have to re-register my number on a new phone). Now my contacts get a "bad key warning". What happens?
Your old key will be invalid and the new key will be sent to your contacts as soon as the contact list will be automatically refreshed. This may take a few hours.
To have the new key take effect immediately the contact list needs to be refreshed manually. To refresh the contact list manually follow this steps:
open the contact list "pencil-icon -> new chat"
click the "three dot menu -> refresh"
And now accept the new key.
BTW. If you have a new phone you can use your already existing account/key by following this tutorial.