Google日本語入力に保存されている過去の変換履歴が多くなると、変換速度が遅くなるようです（筆者の使用感です）。変換履歴を消去すれば速度を回復することができるので、Android5.1の場合で手順を説明します。
なお、この対処法を実行すると、過去の変換履歴が消えますので、ご注意ください。*1
手順
Androidの設定画面で「アプリ」のコーナーを開き、その中の「Google日本語入力」をタップし、次の画面で「アプリを起動する」というタイトルの下にある「起動」をタップ。
すると、「Google 日本語入力設定」という画面が開きます。
その中の「変換」をタップ。すると、「変換」というタイトルの画面が開きます。
その中の、「履歴の消去」をタップ。すると、「履歴の消去」というタイトルの画面になります。
その中の「変換履歴」をタップすると、過去の変換履歴が消去され、その後は変換速度が速くなる（本来の速さに戻る）と思います。
しばらく使っていてまた変換速度が遅くなれば、この作業を再び実行します。
備考
Google日本語入力の「単語リスト」に登録してある単語の数も、変換速度に影響しているかもしれません。不要な単語があれば消しておくのも、変換速度を保つのに有効かもしれません。
*1:消したくない変換履歴があれば、その「変換前」と「変換後」の語句の組み合わせを、Google日本語入力の「単語リスト」に登録しておくことで、変換候補として維持できます。
