I wonder if Signal should expose linked devices directly in the UI at all times. Something like a small icon that indicates "You have 3 linked devices active" or similar.
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.
I think the trouble is information overload is a bit of a thing in this case. It's information that is 99% of the time useless, except the one time it isn't. But also, to an informed user is much less of a threat - the threat is anyone you interact with getting compromised.
EDIT: Like an analytics based approach would probably be far more useful - popping up a confirmation for example if GeoIP shows a device is far removed from all the others, which for most people would be true unless they were traveling.