It would, just not on new devices without moving keys via already-trusted device. This is what WhatsApp presumably does
That's the thing, it does not and it has been known that it does not do this. The keys are stored on the server and the server sends them to your device on login. They do have some kind of machine-id encoded in it, but that is just for show.