In that case, from an existing client with the SSH host key installed, or with your VPS provider's login shell system (if any), read the files '/etc/ssh/ssh_host_$ALGO_key.pub'. Each of these files will yield a line like this:
ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBA4Ljuxwb9ss74agSmMRlBZdnIwMHprWIZ3Ts3G+hxnMmcQxeMAWoA4YXZwbrpQulFjDhjGqQoAGF+MKWXBpaeU= root@ip-172-31-17-215
These are all different hostkeys that the server might give to clients, depending on their mutually-agreed signature algorithm. This is in the same format as a line in the known-hosts file; all you need to do is replace that last bit (in my example, root@ip-172-31-17-215) with the hostname by which you log in (e.g. someserver.example.com). Once you've done that, append the results to the known_hosts file, either for your user account (~/.ssh/known_hosts) or system-wide (/etc/ssh/ssh_known_hosts).
tl;dr: replacing HOSTNAME with the hostname by which you access the server, run the following command on your server and append its output to ~/.ssh/known_hosts on new clients:
cat /etc/ssh/ssh_host_*_key.pub | awk '$3="HOSTNAME"'