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!

**EDIT** Um exemplo de processamento server side retirado diretamente da [documentação do DataTables](http://www.datatables.net/examples/data_sources/server_side.html):

    <?php
     
    /*
     * DataTables example server-side processing script.
     *
     * Please note that this script is intentionally extremely simply to show how
     * server-side processing can be implemented, and probably shouldn't be used as
     * the basis for a large complex system. It is suitable for simple use cases as
     * for learning.
     *
     * See http://datatables.net/usage/server-side for full details on the server-
     * side processing requirements of DataTables.
     *
     * @license MIT - http://datatables.net/license_mit
     */
     
    /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
     * Easy set variables
     */
     
    // DB table to use
    $table = 'datatables_demo';
     
    // Table's primary key
    $primaryKey = 'id';
     
    // Array of database columns which should be read and sent back to DataTables.
    // The `db` parameter represents the column name in the database, while the `dt`
    // parameter represents the DataTables column identifier. In this case simple
    // indexes
    $columns = array(
        array( 'db' => 'first_name', 'dt' => 0 ),
        array( 'db' => 'last_name',  'dt' => 1 ),
        array( 'db' => 'position',   'dt' => 2 ),
        array( 'db' => 'office',     'dt' => 3 ),
        array(
            'db'        => 'start_date',
            'dt'        => 4,
            'formatter' => function( $d, $row ) {
                return date( 'jS M y', strtotime($d));
            }
        ),
        array(
            'db'        => 'salary',
            'dt'        => 5,
            'formatter' => function( $d, $row ) {
                return '$'.number_format($d);
            }
        )
    );
     
    // SQL server connection information
    $sql_details = array(
        'user' => '',
        'pass' => '',
        'db'   => '',
        'host' => ''
    );
     
     
    /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
     * If you just want to use the basic configuration for DataTables with PHP
     * server-side, there is no need to edit below this line.
     */
     
    require( 'ssp.class.php' );
     
    echo json_encode(
        SSP::simple( $_GET, $sql_details, $table, $primaryKey, $columns )
    );