If matrix clients acknowledged new device keys breaking the chain of trust is a fairly normal occurance it'd suck way less. Other encrypted messengers get this, it is a footnote, a little "identity changed" notification if anything. No need to freak out the users about trust over someone losing their old phone.
Security dorks who don't speak normal can take this as confirmation my new matrix keys are authorized by my old established and verified identity.