I used nala package instead of apt-get to fix the issue.
First you have to install it if you can.
sudo apt install nala -y
Then, if you are using ubuntu which in my case was ubuntu jammy, you have to run the command to look for the fastest mirrors
sudo nala fetch --ubuntu jammy
If you are on any other distros, then run sudo nala fetch --help to get how you can complete the remaining part of the command.
I did choose the first 10 mirrors (remember to use spaces when entering multiple mirrors)
However, at some point when I ran sudo nala update there were errors in some of the mirrors. In this case you can go to the /etc/apt/sources.list.d/nala-sources.list file to remove the said mirrors.
sudo nano /etc/apt/sources.list.d/nala-sources.list
Now re-run sudo nala update then try installing the package, either using nala or apt or apt-get.