Касательно именно mysql/innodb - innodb всегда кластеризован по первичному ключу. Поэтому все вторичные индексы всегда указывают на первичный ключ. Что из этого следует:
select time, md5 from img where md5=?
Потребует просмотра всегда двух индексов. Сначала индекса по md5, потом - первичного ключа.
С первичным ключом по md5 этот запрос сделает один просмотр индекса и для вычитывания time, не входящего в индекс, даже не потребует seek - данные лежат непосредственно рядом с листьями первичного ключа. Т.е. от выкидывания суррогатного ключа этому запросу чистый профит.
Не случайно написал time в запросе, если запросить только select md5 или select md5, id - то это будет index only scan по вторичному ключу и сейчас, без обращения ни к первичному ключу ни к самой таблице.
во-вторых,
int - это 4 байта. varchar32 для cp1251 (почему вообще varchar, а не char(32) или вообще binary(16)?) - 32 байта, timestamp 4 байта. Из-за необходимости ссылаться на куда более объёмный первичный ключ, резко увеличатся в объёме все вторичные индексы. Но вторичный индекс у вас останется только один, да один индекс исчезнет, а уникальный немного похудеет за счёт преобразования в первичный. Не столь огромный оверхед получится, вполне можно пережить. Но может быть не столь интересно, если показана часть таблицы и есть кучка других полей и индексов.
Поиск по time чуток просядет, строки сравнивать всё-таки сложнее пары интов. Но на десятке млн записей, да на mysql значения это играть не будет.
в-третьих, innodb оптимизирован под запись последовательно-возрастающих значений. На записи случайных данных несколько просядет производительность. На сколько именно - надо измерять, не помню.
На небольшой табличке всего-то в пару десятков миллионов строк - это значения иметь не будет.