残念ながらレンタルサーバーでMySQLを使用している限り速度アップは難しそうです。
EC-CUBEはMySQLを使用する場合サブクエリを多発します。
これが速度低下の一番の要因ではないかと考えています。
手っ取り早いのはpostgresに変更する事ですが、MySQLを使用するのであれば現在InnoDBになっているテーブルでトランザクションに関係ないテーブルを片っ端からMyISAMに変更し、適切なIndexを設定してあげるか、商品規格まわりのソースをサブクエリを使用しないように大幅に変更する必要があると思います。