MySQL - Estructura recomendada para mayor rapidez

La cuestión es la siguiente:

Poseo una base de datos con varias tablas, de las cuales me importan en este caso solamente 2.

T_Usuario
T_Amigo

T_Usuario
-> Usuario (varchar)
-> Descripcion (varchar)

T_Amigo
-> Usuario (varchar)
-> Amigo (varchar)
-> Fecha (date)

El problema es que T_Amigo alberga ya mas de 150.000.000 de registros, con lo cual las consultas tardan cada vez mas...

Me recomendais que pase a la siguiente estructura?

T_Usuario
-> Id_Usuario (int)
-> Usuario (varchar)
-> Descripcion

T_Amigo
-> Id_Usuario (int)
-> Id_Amigo (int)
-> Fecha (date)

Creeis que este sistema es mas eficiente??

Un saludo y gracias por vuestra ayuda.

Hay que tener en cuenta que también se añaden Usuarios constantemente... si hay que hacer muchos calculos al final... no se que será peor...

Espero vuestras opiniones!

No.Creo que lo máseficiente sería normalizar un poco más (3FN):

T_Usuario
-> Usuario (varchar)
-> Descripcion (varchar)

T_Amigo
-> Amigo (varchar)
-> Fecha (date)

T_Amistad
-> Usuario
-> Amigo

El problema de la tabla T_Amigo puede deberse a que existe la posibilidad que una misma Instancia de Usuario se relacione con n instancias de Amigo y que cada Amigo esté relacionado con n Usuarios, con lo que el crecimiento de la tabla es enorme. En cambio una tercera tabla así puede ser bidireccional.