Eu tive o mesmo problema. A resposta para mim estava no link fornecido por Tomasz. O Tomcat está inicializando o SecureRandom, que é muito lento.
A solução alternativa é usar uma fonte diferente de entropia. Você pode fazer isso fornecendo esse argumento para a JVM do tomcat:
-Djava.security.egd=file:/dev/./urandom
Eu fiz isso criando o script setenv.sh que o tomcat executará automaticamente se existir:
touch /usr/share/tomcat8/bin/setenv.sh
chmod +x /usr/share/tomcat8/bin/setenv.sh
Adicione estas linhas ao setenv.sh e reinicie o servidor
#!/bin/sh
export CATALINA_OPTS="$CATALINA_OPTS -Djava.security.egd=file:/dev/./urandom"