Cem

One verification habit worth adopting: do not test with the tools that bypass the system resolver.

dig and nslookup talk to a nameserver directly and will happily give you a correct answer that has nothing to do with what your applications experience. getent hosts <name> or resolvectl query <name> goes through the actual system path.

More than half the "I changed it and it still does not work" reports I have seen are somebody testing with dig against the old server out of habit.

The distinction that resolves this: supported and enabled by default are two different lists, and the command you ran shows the first one.

Modern SSH clients still contain the code for a number of older algorithms, so they appear when you ask what is compiled in. But they have been removed from the default offer list because they are considered too weak — small key sizes, or hashes no longer trusted. The client will use them only if you ask explicitly, which is exactly what you discovered.

So nothing is inconsistent. The client is saying "I know how to do that, and I will not do it unless you insist." Your config entry is the supported way to insist.

That design is deliberate: it lets old equipment keep working while making sure nobody connects to it weakly by accident.

Before any of that, work out what actually broke, because the answer changes the fix and sometimes there is nothing to reinstall.

The usual causes, in rough order of frequency:

• The system clock is wrong. A certificate that is not yet valid or has expired produces exactly this error. Check the date first — it costs one command and it is the single most common cause, particularly on a virtual machine that has been suspended or on hardware with a dead battery.
• A corporate or VPN client installed an interception certificate and then removed or broke it. You mentioned installing VPN software, which makes this the leading suspect in your case.
• A root certificate genuinely expired. This happens occasionally and breaks old systems that never received the replacement.
• The store was edited or emptied by something well-meaning.

If it is the clock, fixing the clock fixes everything instantly and no download is needed.

Small diagnostic point that generalises well: when a package manager fails, read whether the error is DNS, connection, TLS, or HTTP status — those are four different problems with four different owners.

A 404 is the server telling you your request was understood and there is nothing there. That immediately rules out your network, your resolver and your certificates, which is most of what people check first.