The VPS might still be starting up. Wait 30 seconds and try again. Also verify the IP address is correct.

Check that your IP address is correct. If using a firewall or VPN, try disabling it temporarily. Your provider may need a few minutes to provision the server.

This first connection step expects password login, so the SSH command should not include -i yet. Try ssh root@YOUR_IP. If the server still says publickey and never asks for a password, use your provider console or recreate the VPS with root password login enabled. If only root login is disabled, try ssh ubuntu@YOUR_IP, run sudo -i, and continue only after the prompt ends with #. A sudo password prompt wants the ubuntu Linux account password, not a provider website password or a different root password.

If you recreated your VPS, the old key is cached. Run: ssh-keygen -R YOUR_IP then try connecting again.