It turned out that ARM decided to make our life easier (sarcasm) by deprecating the use of PPA - their page at launchpad now has an anouncement: "... all new binary and source packages will not be released on Launchpad henceforth ...".

So, to make use of their latest arm-none-eabi-gdb you have to install gcc-arm-embedded manually.

Remove arm-none-eabi-gcc from your system:

sudo apt remove gcc-arm-none-eabi

Download latest version (Linux x86_64 Tarball) from their website, check its MD5. Unpack it into some directory. I used /usr/share/ :

sudo tar xjf gcc-arm-none-eabi-YOUR-VERSION.bz2 -C /usr/share/

Create links so that binaries are accessible system-wide:

sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-gcc /usr/bin/arm-none-eabi-gcc 
sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-g++ /usr/bin/arm-none-eabi-g++
sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-gdb /usr/bin/arm-none-eabi-gdb
sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-size /usr/bin/arm-none-eabi-size
sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-objcopy /usr/bin/arm-none-eabi-objcopy

Install dependencies. ARM's "full installation instructions" listed in readme.txt won't tell you what dependencies are - you have to figure it out by trial and error. In my system I had to manually create symbolic links to force it to work:

sudo apt install libncurses-dev
sudo ln -s /usr/lib/x86_64-linux-gnu/libncurses.so.6 /usr/lib/x86_64-linux-gnu/libncurses.so.5
sudo ln -s /usr/lib/x86_64-linux-gnu/libtinfo.so.6 /usr/lib/x86_64-linux-gnu/libtinfo.so.5

Check if it works:

arm-none-eabi-gcc --version
arm-none-eabi-g++ --version
arm-none-eabi-gdb --version
arm-none-eabi-size --version

On Debian and derivatives, the package you’re looking for is gcc-arm-none-eabi:

apt install gcc-arm-none-eabi

To find this out yourself in future, install apt-file, update your indexes and use it to search for commands:

apt install apt-file
apt-file update
apt-file search bin/arm-none-eabi-gcc

I found the solution based on the discussion available at https://unix.stackexchange.com/questions/377345/installing-arm-none-eabi-gcc and the documentation available on https://mynewt.apache.org/latest/get_started/native_install/cross_tools.html#installing-the-arm-cross-toolchain.

The name and structure of the software changed over time. The arm-none-eabi-gcc is gcc-arm-none-eabi now, and so on.

$ sudo apt-get remove binutils-arm-none-eabi gcc-arm-none-eabi
$ sudo add-apt-repository ppa:team-gcc-arm-embedded/ppa
$ sudo apt-get update 
$ sudo apt-get upgrade
$ sudo apt-get install gcc-arm-none-eabi
$ sudo apt-get install gdb-arm-none-eabi 

And finally, to verify the downloads, you can run the following commands:

arm-none-eabi-gcc --version
arm-none-eabi-g++ --version
arm-none-eabi-size --version