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!