Experimente um apt-get update
rápido para obter as listas de pacotes mais recentes de repos e, em seguida, apt-cache search openjdk
para verificar qual a versão mais recente oferecida disponível para você, se houver.
Provavelmente, se esta for uma nova instalação básica, você terá que acessar o /etc/apt/sources.list
e certificar-se de ter as listas de pacotes não-livres ativadas, que não estão ativadas por padrão no Debian, acredito. Então, verifique isso Como habilitar pacotes não-livres no Debian?