Sounds like the server you inherited is running a very old version of Debian. If, as you say, it hasn't been upgraded for 10 years, it's probably running Squeeze or Wheezy. Both of these are ancient and really shouldn't be in production use on the public internet.
It's impossible to give you complete step-by-step instructions on what to do with your server, so here's a few useful tips:
The ...no matching key exchange method... error message is because the server is running an old version of sshd, with deprecated ciphers and key exchange methods.
You should upgrade this as soon as you can (there were good reasons for the obsolete ciphers to be deprecated) but in the meantime, you can configure your local ssh client to always use diffie-hellman-group1-sha1 and aes128-cbc when connecting to your server. edit ~/.ssh/config and add the following:
Host your_server_name KexAlgorithms diffie-hellman-group1-sha1 Ciphers aes128-cbc
You could also use your server's IP address instead of (or as well as) "your_server_name". BTW, don't forget to undo this after you've upgraded sshd on your server to a modern version.
If your server is running Debian, you will be able to upgrade it....and upgrading it remotely via ssh from the bash command line is no problem. You'll have to use apt, apt-get, aptitude or other command-line tools instead of graphical tools like synaptic but Debian was designed to be upgraded in-place like this.
The recommended procedure is to upgrade it one version at a time, from whatever it is currently running to the next version. e.g. if it currently has Debian 6 ("Squeeze") installed, you would upgrade it to Debian 7 ("Wheezy"), then to Debian 8 ("Jessie"), and so on until it was running Debian 11 ("Bullseye"). There's a good summary of Debian's release history and version numbering/naming at https://en.wikipedia.org/wiki/Debian_version_history
BTW, by "recommended procedure", I mean that Debian only really guarantees a successful upgrade from one release version to the next. In some cases, it is possible to jump two or more releases at a time, but I advise against even thinking about attempting to do that, especially if you don't have physical access to the machine, and especially when the installed Debian release is so ancient. Attempting this will be very likely to result in a broken (and possibly unfixable) system.
There will probably be several things that need to be manually reconfigured on every upgrade. Most packages will be fine, but some will have incompatibilities, new features, and/or deprecated old features in various daemons that are installed (e.g. sshd, apache, nginx, squid, postfix, or whatever else is installed).
Note: the main debian archives only have repos for the current stable release (Bullseye) and oldstable (Buster). Older releases are available on https://www.debian.org/distrib/archive and you will have to use archive.debian.org URLs (or a nearby mirror of it) in your sources.list URLs.
For example, instead of something like deb http://ftp.au.debian.org/debian/ wheezy main contrib non-free, you'd have to use deb http://archive.debian.org/debian/ wheezy main contrib non-free
Whenever you upgrade sshd, I very strongly recommend testing that the new version works correctly by trying to ssh in from another terminal window or tab. Do not log out of your current ssh session until you have verified that the new version of sshd works otherwise you may not be able to log back in - at some point (I can't remember exactly which version), the new sshd will no longer support the old ciphers or key exchange methods, so you will have to undo the configuration changes you made to your ~/.ssh/config. You will probably have to make minor changes to /etc/ssh/sshd_config on your server at some point, too.
This is extremely important and very much worth repeating:
Do NOT logout of your ssh session until you've confirmed that you can login again.
Instead of upgrading through multiple versions of Debian, you may find it easier to just backup your data and config files, wipe your server, do a fresh install of Debian 11, and then restore your data and config files. If it's only running a few important services, probably much easier.
An even better alternative would be to rent a second hosted server, install Debian 11 on it, and gradually migrate services from the old server to the new. This is probably the easiest method, and least prone to problems or failure - you can migrate each service one at a time AND test that each new service works before cutting over to it. It gives you time to think and avoid the kind of mistakes you might make in a panic or under extreme time pressure.
Either way, you're going to need to have a comprehensive list of exactly what it's running and why - and how important it is for each service to keep running on that particular machine or whether it can be retired or migrated to another machine. Having a good understanding of what those programs do, how they work, and how to configure them will also be important.
Some of this you can get by investigating the system and its config files, and some you can only get by talking to people in your organisation and getting someone senior to make decisions about the importance and priorities of particular services - the upgrade process is going to be long and tedious and there will be at least temporary breakage at various stages so CYA by getting a manager to make the decisions. Remember that nobody notices when a sysadmin does a good job, but everybody notices when things break.
In short, don't just jump into the upgrades without thorough planning. You will need to plan each step of the upgrade, and that plan should include testing that each important service is still running correctly after each upgrade.
Backup everything before doing anything. Also, if the machine is running RAID of any kind, remember that RAID is not a substitute for backups. There is no substitute for backups. If your server doesn't currently have a regular backup schedule, then setting one up should probably be the second thing you do. The first should be making a current backup.
You should practice the upgrade by installing Squeeze or Wheezy on a VM and then going through the process of upgrading it all the way up to Bullseye. It won't be exactly the same as upgrading your real server, but at least you'll become very familiar with the process. You can take a snapshot of the VM before each upgrade step, so you can revert if anything goes wrong that you can't easily fix.
Every Debian release comes with upgrade notes telling you about major changes and incompatibilities. You should read these before each upgrade.
