Getting an error when running apt update: ModuleNotFoundError: No module named 'apt_pkg'

When I run apt update on a Ubuntu 18.04.6 LTS, which is a server my company use for hosting Netbox, I get the following issue:

$ sudo apt update
Hit:1 http://azure.archive.ubuntu.com/ubuntu bionic InRelease
Hit:2 http://azure.archive.ubuntu.com/ubuntu bionic-updates InRelease
Hit:3 http://azure.archive.ubuntu.com/ubuntu bionic-backports InRelease
Hit:4 http://ppa.launchpad.net/deadsnakes/ppa/ubuntu bionic InRelease
Hit:5 https://packages.microsoft.com/ubuntu/18.04/prod bionic InRelease
Hit:6 http://security.ubuntu.com/ubuntu bionic-security InRelease
Traceback (most recent call last):
  File "/usr/lib/cnf-update-db", line 8, in <module>
    from CommandNotFound.db.creator import DbCreator
  File "/usr/lib/python3/dist-packages/CommandNotFound/db/creator.py", line 11, in <module>
    import apt_pkg
ModuleNotFoundError: No module named 'apt_pkg'
Reading package lists... Done
E: Problem executing scripts APT::Update::Post-Invoke-Success 'if /usr/bin/test -w /var/lib/command-not-found/ -a -e /usr/lib/cnf-update-db; then /usr/lib/cnf-update-db > /dev/null; fi'

I get a similar issue when I run neofetch:

$ neofetch
Traceback (most recent call last):
  File "/usr/lib/command-not-found", line 28, in <module>
    from CommandNotFound import CommandNotFound
  File "/usr/lib/python3/dist-packages/CommandNotFound/CommandNotFound.py", line 19, in <module>
    from CommandNotFound.db.db import SqliteDatabase
  File "/usr/lib/python3/dist-packages/CommandNotFound/db/db.py", line 5, in <module>
    import apt_pkg
ModuleNotFoundError: No module named 'apt_pkg'

A colleague of mine told me to run these and try again, but I got the same issue:

sudo apt-get remove command-not-found
sudo apt-get clean
sudo apt-get update
sudo apt-get install command-not-found

Then I went to check how many python version are installed on this server, and I count 4:

$ ls -ls /usr/bin/python*
   0 lrwxrwxrwx 1 root root       9 Apr 16  2018 /usr/bin/python -> python2.7
   0 lrwxrwxrwx 1 root root       9 Apr 16  2018 /usr/bin/python2 -> python2.7
3544 -rwxr-xr-x 1 root root 3628904 Nov 28 18:51 /usr/bin/python2.7
   0 lrwxrwxrwx 1 root root      25 Jan 10 08:10 /usr/bin/python3 -> /etc/alternatives/python3
   0 lrwxrwxrwx 1 root root      16 Oct 25  2018 /usr/bin/python3-config -> python3.6-config
   4 -rwxr-xr-x 1 root root    1018 Oct 28  2017 /usr/bin/python3-jsondiff
   4 -rwxr-xr-x 1 root root    3661 Oct 28  2017 /usr/bin/python3-jsonpatch
   4 -rwxr-xr-x 1 root root    1342 May  1  2016 /usr/bin/python3-jsonpointer
   4 -rwxr-xr-x 1 root root     398 Nov 15  2017 /usr/bin/python3-jsonschema
5356 -rwxr-xr-x 1 root root 5481816 Dec  7 01:11 /usr/bin/python3.10
4424 -rwxr-xr-x 2 root root 4526456 Nov 25 14:10 /usr/bin/python3.6
   0 lrwxrwxrwx 1 root root      33 Nov 25 14:10 /usr/bin/python3.6-config -> x86_64-linux-gnu-python3.6-config
4424 -rwxr-xr-x 2 root root 4526456 Nov 25 14:10 /usr/bin/python3.6m
   0 lrwxrwxrwx 1 root root      34 Nov 25 14:10 /usr/bin/python3.6m-config -> x86_64-linux-gnu-python3.6m-config
   0 lrwxrwxrwx 1 root root      10 Oct 25  2018 /usr/bin/python3m -> python3.6m
   0 lrwxrwxrwx 1 root root      17 Oct 25  2018 /usr/bin/python3m-config -> python3.6m-config

Running python3 --version it returns Python 3.10.9

Does anyone have a clue how can I resolve this issue without having to migrate the hosted app? That would be a nightmare :(

EDIT:

I moved to /usr/lib/python3/dist-packages looked for apt_pkg via ls -la | grep "apt_pkg.cpython" and found the file apt_pkg.cpython-36m-x86_64-linux-gnu.so, I renamed the file to apt_pkg.so and now I could run apt update with a new error message:

$ sudo apt update && sudo apt upgrade
[sudo] password for admin-federico-dostuni:
Hit:1 http://azure.archive.ubuntu.com/ubuntu bionic InRelease
Get:2 http://azure.archive.ubuntu.com/ubuntu bionic-updates InRelease [88.7 kB]
Get:3 http://azure.archive.ubuntu.com/ubuntu bionic-backports InRelease [83.3 kB]
Hit:4 http://security.ubuntu.com/ubuntu bionic-security InRelease
Hit:5 http://ppa.launchpad.net/deadsnakes/ppa/ubuntu bionic InRelease
Hit:6 https://packages.microsoft.com/ubuntu/18.04/prod bionic InRelease
Fetched 172 kB in 1s (176 kB/s)
Reading package lists... Done
Building dependency tree
Reading state information... Done
All packages are up to date.
Reading package lists... Done
Building dependency tree
Reading state information... Done
Calculating upgrade... Done
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
1 not fully installed or removed.
After this operation, 0 B of additional disk space will be used.
Do you want to continue? [Y/n] y

Setting up update-notifier-common (3.192.1.15) ...
Traceback (most recent call last):
  File "/usr/lib/update-notifier/package-data-downloader", line 24, in <module>
    import debian.deb822
  File "/usr/lib/python3/dist-packages/debian/deb822.py", line 78, in <module>
    class TagSectionWrapper(collections.Mapping):
AttributeError: module 'collections' has no attribute 'Mapping'
dpkg: error processing package update-notifier-common (--configure):
 installed update-notifier-common package post-installation script subprocess returned error exit status 1
Errors were encountered while processing:
 update-notifier-common
E: Sub-process /usr/bin/dpkg returned an error code (1)