Index for VARCHAR column has low efficiency I have two tables with relationship one to many.

create table locations
(
  id bigint 
     auto_increment 
     primary key,
  location_id varchar(128) 
     null,
  constraint locations_location_id_uindex 
     unique (location_id)
);


create table links
(
  id bigint 
     auto_increment 
     primary key,
  location_id varchar(128) 
     null,
  loc_id bigint 
     null,
  constraint links_location_id_fk 
     foreign key (loc_id) 
     references locations (id)
);

create index links_location_id_index
   on links (location_id);


The locations table has 596_752 records and links table has 1_221_450 ones.  Both tables are very often updated with a new data, there is no a deletion process. The location_id in both tables has size 30 characters.
When a new data appear in links table I have to find all links.location_id that do not exist in locations.location_id. In order to do so I execute the following query:

SELECT links.location_id 
FROM links
LEFT JOIN locations l 
   ON links.location_id = l.location_id
WHERE l.location_id IS NULL


The log output says:

34 rows retrieved starting from 1 in 1 m 11 s 678 ms (execution: 1 m 11 s 668 ms, fetching: 10 ms)


As you can see, it works too long and I am looking for a way how to improve it, can You help me?

EDIT
The info about MySQL server, it's db.t2.micro AWS instance:

innodb_version  8.0.13
protocol_version    10
slave_type_conversions  ""
tls_version TLSv1,TLSv1.1,TLSv1.2
version 8.0.13
version_comment Source distribution
version_compile_machine x86_64
version_compile_os  Linux
version_compile_zlib    1.2.11
Would you try this and let me know if this improves your performance:

SELECT links.location_id FROM links 
WHERE NOT Exists( 
select location_id from locations);