This type of behavior is caused by a tool frequently installed on some distributions that hook into bash. This hook makes it so that if you try to run a command, and the command doesn't exist, then bash will search the files available in the configured repositories, and tell you what package you would need to install to get that command.
If you are not on a Debian system you'll want to look at your bash startup files profiles and so on and see if anything defines the function named
command_not_found_handle. If that bash function is defined, then it will be called whenever you run a command and an appropriate program cannot be found in your search path. If you run
typset | less and browse through the output you will see the
command_not_found_handle() function if it has been defined.
On Debian/Ubuntu the package that provides this behavior is command-not-found. If you purge that, then you will disable the lookups which does slow things down.
Here is an example
# command-not-found installed
$ time pwgen
The program 'pwgen' is currently not installed. To run 'pwgen' please ask your administrator to install the package 'pwgen'
pwgen: command not found
# purge command-not-found and restart bash
$ time pwgen
-bash: pwgen: command not found
The exact time would of course be different for you. I ran my tests on a pretty beefy server.