Если в таблице всего лишь 13 млн записей и мы просто берём 1 строку через select where user_id = id limit 1 и такой запрос длится более 5-6 секунд то это значит что vds-ка гавно?

И это в laravel через связь один ко многим.

vds 2 ядра по 3ггц 2гб оперативки.

Говно

Мне кажется заявленных мощностей не предоставляют.

Лучше 8 ядер, по 2.44ц и 16(8)GB оперативки.

Скорее всего. Linux?

Face ID, Да

Face ID, Если будет столько мощности, то запрос выполнится быстрее?

Это уже сервер отдельный.