Why is sudo taking way too long?
ErikMH's answer gave me the idea to first just try to revert the sudoers file, without reverting/upgrading my whole system again. So in short:


Run this to get a root shell: sudo -s
Make a copy of /private/etc/sudoers
Run: cp /private/etc/sudoers\~orig /private/etc/sudoers
Fix permissions by running: chmod 440 /private/etc/sudoers ; chown root:wheel /private/etc/sudoers
Move any files in /private/etc/sudoers.d/ away from there
Test out sudo in another terminal
Don't forget to exit this shell to prevent inadvertently running commands as root when you don't mean to


Now running sudo should work again.

Next step is to check the differences between the old sudoers file (you copied away in step 2) and the current one and add those changes step by step back to /private/etc/sudoers or /private/etc/sudoers.d/, each time running a command using sudo to check if the change breaks it.

In my case, I had specified a nonexistent group in the sudoers file. Correcting that fixed my issue.