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.