Tiago, da maneira que você está fazendo o que acontece é o seguinte;

1- Você faz um request no servidor  
2- Você busca todos os 5k registros no banco de dados  
3- Você renderiza um HTML gigantesco com todos os milhares de registros  
4- O browser recebe os dados e gasta muito tempo aplicando a DataTables em todos esses registros

**Primeiro gargalo:** Item 3 - O trafego de tantos dados pode estar aumentando o tempo até que a página fique pronta

**Segundo gargalo:** Item 4 - O tempo para aplicar o DataTables provavelmente esta tornando 90% deste tempo.

*PS.: Possível gargalo no item 2 dependendo de como a sua aplicação esta implantada*

O fato é, muito dificilmente o usuário vai consumir 5k registros todas as vezes que abrir a sua página, portanto a melhor abordagem na minha opinião é;

1- Você recebe um request e devolve uma página basicamente vazia, contendo apenas a estrutura da tabela HTML vazia, onde voce vai aplicar o DataTables  
2- Assim que o browser receber o HTML e a página estiver pronta (em `$(function() {});` por exemplo) você chama o DataTables passando os parâmetros para utilizar a paginação nativa deles, ou seja:

    $('table.dataTable').DataTable({
        displayLength: 15, //Começaremos com apenas 15 registros
        serverSide: true,  //Quem vai tratar a interação com a tabela é o servidor
        paginate: true,    //Queremos paginas
        filter: true,      //Queremos que o usuário possa procurar entre os 5k registros
        ajax: {
            url: 'filtragemDeRegistros.php' //O seu script que vai filtrar os dados do lado do servidor
        }
    });
  
Acontece que agora você precisa implementar a lógica de filtragem no backend. Para você descobrir quais parâmetros o DataTables passa para o servidor você pode pesquisar a documentação na pagina oficial do DT ou simplesmente imprimir no console do servidor o request enviado.

Voce vai gastar um tempinho implementando mas vale a pena e a app vai carregar muito mais rápida.

Ps.: A doc do datatables ensina detalhadamente tudo isso, gaste um tempo lendo!