Adicionar chaves primárias em tabelas deixa as consultas mais lentras

Olá, boa tarde!

Estou com um problemão...

Peguei umas páginas em ASP para fazer manutenção por elas estarem lentas, e logo fui fazer a manutenção na base de dados dela, já que não possuia nenhuma chave primária.

Acontece que quando adiciono as primary keys, a página fica ainda mais lenta!

Fiz testes definindo e removendo as chaves e isso realmente acontece!

O que explica isso? Desconsiderem possibilidade de resultados já estarem em cache...

A consulta é feita por SQL dentro do código ASP, e não por stored procedure.

Obrigadao!