MySql için 5 milyon komik bir rakam, burada mysql in değil, veritabanını tasarlayanın mimari hatası vardır.

Kayıt adedi değil, mimari hatalar yavaşlatır.
Tablolarınızda gerekli indeksleri oluşturdunuz mu ? (id haricinde)

Şuan da kullandığım 200 milyonun üzerinde satır olan, 6GB civarı veritabanı oldukça hızlı çalışıyor.
Mysql küçümsenecek bir veritabanı yazılımı değildir.