Would probably lead to notification fatigue.

Showing a big snackbar when a new device is added is probably enough, especially if the app can detect there was no "action" on your phone that triggered it.

Key transparency, once rolled out, would help to ensure there is no lingering "bad" device around, but phishing will always be a problem.