仮想マシンを作り直す必要はありません。
コンソール経由で仮想マシンにログインして、秘密鍵を再作成してください。
ただし、コンソールにログインする際はパスワードが必要です。
パスワードが不明な場合は、コンソールのログイン画面より「パスワードを忘れた」をご確認の上、一度パスワードリセットしてから行ってください。
新たにOS上で SSHKey を作成し、仮想マシン上の authorized_keys に公開鍵を登録する場合、下記FAQに記載の対処を実施しない場合は、再起動後に古い SSHKey が末尾に自動で追記されてしまいます。
併せてご確認ください。