Thank you for trying to help me.
Explain query:
And the other query (6,5 min):
Here is the one with the "fix" from OP (11 min):
Is there any other way we could get it faster?
I've never had problems before upgrading to Debian 8 with MySQL version 5.4/5.5