но даже после добавления ключей и запросов по этим ключам всё равно получается, что затрагивается огромное кол-во строк
этот explain надо еще научиться читать.
Вот неплохая статья для старта, особо присмотритесь к колонке type
https://mattweb.ru/moj-blog/bazy-dannykh/item/65-i...
Потом постарайтесь построить такие индексы, чтобы свести type к наилучшему варианту.
При этом не стоит забывать, что большое кол-во индексов замедляет вставку (и занимает место на дисках, но это скорее мелочь).