こんにちは、平塚といいます。

2015年4月8日 21:39 二見　修康[ＤＮＰデジタルコム] <futami-n2@xxxxxxxxxx>:
> 件数が増えるごとに登録が徐々に遅くなり
> １億3000万件越えた辺りから極端に遅くなってきます

> 何か他に良い方法は無いでしょうか？

パーティショニングを試されてはいかがでしょうか。

MyNAのページから、松信さんのスライド
http://www.mysql.gr.jp/frame/modules/bwiki/index.php?cmd=read&page=matsunobu

MySQLパフォーマンスチューニングとよくある落とし穴
(2009.6 MySQLパフォーマンスセミナー)

の、P23をご参照ください。