De acordo com o DistroWatch , o Ubuntu Xenial vem com o Python 3.5.1, que parece atípico quando comparado a outros lançamentos comumente sendo empacotado com 2.XX
Consulte os comentários em esta pergunta por que o Python 2 é chamado pelo comando python no Ubuntu. A resposta principal recomenda usar um alias para chamar o Python 3 com python , em oposição a usar links simbólicos e quebrar coisas que usam no Python 2. Embora eu suponha que não ter o Python 2 instalado prejudique o propósito dessa precaução, e o symlinking pode ser uma solução viável.
Tem certeza de que ansible não está procurando pelo Python 2? Aqui é um link muito recente para a documentação deles sobre o próximo suporte do Python 3.