Boot from a rescue volume, or use the VPS provider's root password reset functionality.

terminate and launch a new one? You have automation to provision your servers right?