Long page generation time when banlist is long

In 3.0 when the banlist table had many rows the pages which displays the banlist was still generated very fast.
However in 3.1 the pages are generated very very slow.
For example:
3.0 - 24219 rows

Page generated in 1.2381 seconds with 4 queries + 2 queries returning data from cache

Time spent on mysqli queries: 0.19001s | Time spent on PHP: 1.04806s

3.1 - 5770 rows

Page generated in 11.0586 seconds with 5 queries + 1 query returning data from cache

Time spent on mysqli queries: 0.076s | Time spent on PHP: 10.98263s

Although the 3.1 board has way less rows it tooks about 10x longer.

Originally mentioned here: https://www.phpbb.de/community/viewtopic.php?f=33&t=231868 (german)