結論から言うとinit時に–no-rehashを付け足すといいらしい。
これがないと毎回ターミナル起動時にrehashが呼ばれるため遅くなるようだ。

eval "$(anyenv init - --no-rehash)"