That's the approach I use with Linode. Unlike EC2 there's no browser-viewable system-log that shows the public key, but it can be retrieved using a web-based terminal session.

To find the fingerprint in PuTTY's obsolete format, the command I use is equivalent to the one you've given. It was provided in the ServerFault answer I linked:

     ssh-keygen -l -E md5 -f /etc/ssh/ssh_host_ed25519_key.pub

I don't like comparing fingerprints by eye, but PuTTY doesn't make it easy to do otherwise. This issue doesn't arise with PowerShell's OpenSSH client, where I can just copy the fingerprint (in the new format) to the clipboard. (It lacks features like mouse support though, so I prefer to use PuTTY.)

To find the fingerprint in the new format for OpenSSH, I believe the command is:

    ssh-keygen -l -f /etc/ssh/ssh_host_ed25519_key.pub

> I believe that this method provides as much chain of trust as possible.

Yes, can't do better than that. If your HTTPS session with your VPS provider has been compromised, it's all over anyway.