Search autocomplete - what is the proper way to make it work for more that 13000 nodes?
I have not run into this directly with Search Autocomplete, but have run into similar issues with Views autocompletion with very large node sets.  There are two things that have helped me in the past.

One, is to make sure your database is truly optimized, to eliminate that from any speed problems.  mysqltuner will give you a good starting point.

The second thing requires monkey patching misc/autocomplete.js to use your own version of Drupal.ACDB.prototype.search which uses a minimum search needle length to lower the initial result set.  TBH, I have done this before, but it was so long ago that I forget the details.

Also keep in mind that single word searches will be against the index (which has a MySQL index), but multiword searches are against the dataset, which is essentially a LIKE query, which can be slow.  Enable query profiling to see what is going on there.

This should give you a starting point.