Ok, percebi:
sudo apt remove --purge openjdk-8-jre-headless
sudo apt autoremove
sudo apt install --reinstall openjdk-8-jre-headless
Agora eu recebo como esperado
~$ java -version
openjdk version "1.8.0_131"
OpenJDK Runtime Environment (build 1.8.0_131-8u131-b11-2ubuntu1.16.04.3-b11)
OpenJDK 64-Bit Server VM (build 25.131-b11, mixed mode)