I have an iPhone 5s that I recently sold out after removing myself completely from it. I literally erased all data from it, and did a factory reset so that it didn't remember me. Now, when I go to Find My iPhone, I get notified that you have to authenticate using some devices, I still see that old iPhone listed as iPhone (4) in there and it doesn't make sense because I remove it already from it. How do I remove this iPhone?
Login to appleid.apple.com, Passwords/Security/Manage Trusted Devices. You should be able to remove your old device there.