"Couldn't verify username because servers are unavailable" when connecting to Minecraft Java server in online mode

I’m using a server I bought a while ago to run a Minecraft server for my friends, and while setting it up, I had an issue where whenever I connected, it said "Authentication servers are down. Please try again later, sorry!" The server logs would also show the message: "Couldn’t verify username because servers are unavailable." Clearly this wasn’t an issue on Mojang’s end, because I could connect to other servers, and I could also ping authserver.mojang.com.

For the time being, I have set online-mode=false, though I am controlling access using a whitelist. For reasons of both security and features (like skins), I’d like to switch to online mode. Any ideas on how to start troubleshooting? I imagine if there was a way to make the logs more verbose that would help.

OS is Debian 9, Minecraft Server version is 1.16.4. I have both OpenJDK 1.8.0_275 and 11.0.6 (from backports) installed; currently I am using 1.8.0_275 but the same issue occurs on both versions. At the moment I have no hardware or software firewalls.