Same thing happened to me. I set the new router to have the same SSID/PW as the previous one. A former tenant came by to pick up some of her mail and her phone connected. Since the new router had never seen her phone before, it showed up as an unregistered device.
If you are worried, change your Wi-Fi password.
Do you have a Guest Wi-Fi without password? Or friends you have shared a password with?
Finally, and this is complete surmise on my part, is devices have to connect to a Wi-Fi signal in order to do a password exchange, even if unsuccessful, which may be recorded by your device.