Paginate performance issue
Add the following tags around your {% pagination %}

{% cache %}
{% endcache %}


Those tags will refresh every time the content changes, and when the content hasn't changed, it'll reduce your database queries significantly.

For more info see:


The craft docs
What are the best practices for using the cache tag