5000 linhas por 50 colunas não é uma planilha grande. 12MB é um tamanho de arquivo pequeno / médio perfeitamente razoável e você não deve precisar fazer nada tão drástico como retrabalho para um banco de dados ou algo semelhante.
A partir da sua descrição, o problema parece ser os links. Quão grandes são as pastas de trabalho referenciadas? Eles estão recalculando quando você se conecta a eles? Eu gosto da ideia de pré-abertura: você pode ver o que está acontecendo.
O seu uso de memória (veja o Gerenciador de Tarefas) está excedendo sua RAM física disponível? Uma vez que a memória tem que ser trocada para o disco, as coisas começam a desacelerar muito.
Além da ajuda de pré-abertura e classificação, sugiro dar uma olhada nas fórmulas que não são de pesquisa: qualquer uma pode ser convertida em fórmulas de matriz e chamada uma vez por cálculo, em vez de uma vez por linha?
Na coisa do VLOOKUP: você já tentou usar INDEX(value_range, MATCH(lookup_key, key_range))
? Existem situações em que é mais rápido.
Você não diz se tem algum VBA. Se fizer isso, observe quantas vezes as funções do VBA são chamadas e quanto tempo elas levam. Código VBA que faz muita referência a objetos do Excel pode ser caro.