Public-key identity verification wouldn't even require substantial upgrades to anything except the phone hardware itself - when making the call, just convey the

Public-key identity verification wouldn't even require substantial upgrades to anything except the phone hardware itself - when making the call, just convey the signature upon connection via a dialup-modem-like encoding, and the receiver may at their discretion neglect to connect their audio hardware to the line until after verifying that data. (Could even use some kind of PoW as another option, for calls where the receiver is unlikely to have received your public key yet.)