Is it normal that bash stat() and access() much, before commands?

You should look at the loop in findcmd.c:find_user_command_in_path().

stat() is called (from file_status()) twice for each element in path: once via find_in_path_element() at line 640 and once via is_directory() at line 645.

As you mentioned, it's also in file_status() that eaccess() is called.

While that could be optimized, keep in mind that it's not big deal, because the path is then hashed, and all this searching and stat'ing happens only the first time a command is used.