Is it possible to hold a server hostage if someone is given root access? If I have a VPS (on digital ocean) running debian and I share root access to this server via SSH keys or root password with someone, can that person hold my website (the thing that is being hosted on the server) hostage? That is, they have as much access as I do. Can't I just reset root password and remove all SSH keys to ensure it is safe again? Otherwise, could I just spin up a new VPS and re-upload all the site code/database and start fresh? Someone told me the only solution was to throw everything away including the code (magento php code) on the server and start from scratch, but I think this is overkill.

On DigitalOcean you can login as root from the DO console (and you don't need to share the access to that). Otherwise you can also destroy the droplet and rebuild one from your non-DO-hosted backups (because you have these of course :)) or from the DO snapshots (if you paid for that), or a mix of the two (snapshots are done weekly)(*). If you have a domain you can also change the domain to point to a completely different machine.

Yes, in the general case, when you have been hacked the only way to have a complete trust in the system is to rebuild it from scratch, but then it also depends what you use it for, how critical it is and who hacked you. The hostage taker is a rather "benign" case because he does everything in plain sight. The real baddie is the one who hacks your system and uses it for his own purposes behind you back.

(*) of course all this assumes that you keep the backups of the past days/weeks, otherwise your only backup will be the encrypted version...