A new pair of keys are also generated when a device is wiped and restored from backup (in my experience on iOS).