Duas opções a considerar:

1) o mais fácil é incluir várias linhas de valores em uma inserção. Isso é muito, muito mais rápido do que fazer várias inserções.

Insetad de fazer INSERT INTO tbl ( cols ) VALUES ( vals ) , faça algo como INSERT INTO tbl ( cols ) VALUES ( vals ), ( vals ), ( vals )

A quantidade de linhas que você pode inserir de uma vez depende do tamanho máximo do pacote do servidor mysql, mas você provavelmente pode fazer 100, 1000, talvez 10000 linhas com segurança e isso deve fornecer um aumento de desempenho de uma ordem de magnitude ou mais.

Consulte http://dev.mysql.com/doc/ refman/5.5/en/insert-speed.html

2) LOAD DATA INFILE é um pouco diferente, requer mais trabalho e tem seus próprios requisitos, mas é muito, muito rápido.