First of all, It was good point about reinstalling server from scratch.
If you have set your encrypted root password in /etc/shadow, there is no efficient way to guess It, because It is encrypted using cryptographic hash function. If you have set it to some plaintext value, the password will be threated as invalid and will not be accepted anyway, because passwords in shadow database are stored in particular format.
If you have physical access to server, you can reboot In single user mode via bypassing kernel option single
(or init=/bin/bash
for Ubuntu), there is a tutorial. Then you can change your root password by using passwd
and reboot system to access it as usual.
The good practice is to avoid root access via ssh and use sudo to gain superuser privileges. Also you can disable password authentication for OpenSSH and switch to Public key authentication.
UPD: I don't have enough reputation to answer to your comment, so updating the answer: you can boot to single user mode by changing kernel boot parameters in bootloader. It doesn't require password unless you had set up the one for Grub. Please check out the tutorial I've mentioned above to perform single user boot.