I have heard of Nala before but have never actually taken the time to install it. Based on your comment, I just checked it out on one of the Debian 12 systems I run. Turns out it was right in the repos.
Wow. So good. I cannot believe it took me this long. Jealous of it on the Arch installs now.
I installed it on Ubuntu 22.04 as well but it was not there when I searched. I had to add the jammy-backports repo first.