No, hold on. That's not what I implied. My understanding is that the private key is stored on your own device, unless you decide to use something like iCloud K

No, hold on. That's not what I implied. My understanding is that the private key is stored on your own device, unless you decide to use something like iCloud Keychain (which should be encrypted). The public key, on the other hand, is stored on the service providers' servers. That is used to create a "challenge", which I guess on your phone you will need to "decrypt/sign" with the private key to prove that "it's really you". That's how I understand it.