apt-get update is slow after 19.04

It seems that your command-not-found package is corrupted somehow. You could purge it, remove its configuration, reinstall it and then reconfigure it as well as finally update it with:

sudo aptitude purge command-not-found
sudo aptitude purge ~c command-not-found
sudo aptitude install command-not-found
sudo dpkg-reconfigure command-not-found
sudo update-command-not-found

These are the files the command-not-found package contains: https://packages.ubuntu.com/en/disco/all/command-not-found/filelist

Good luck.