En lugar de hacer lo que has hecho podrías tener un array en el que cada posición representa una letra, la posición 0 la 'a', la 1 la 'b'...etc, el array será de enteros y mientras recorres la frase vas sumando los valores del array correspondientes.
El código podría ser algo así: (te lo pongo en pseudocódigo para que tú lo hagas en C)
CADENA frase; //Variable
ENTERO array[27]; //Variable, posiciones para a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
inicializar(array); //Poner a 0 todas las posiciones del array
LEER(frase); //leemos la frase de la entrada estandar
toLower(frase); //Convierte la frase a minúscula
PARA CADA caracter DE frase HACER
array[caracter-97]++;
ImprimirArray(array); //Imprimimos los valores del array que sean distintos de 0
Lo de caracter-97 lo hacemos porque la 'a' en código ASCII tiene el valor decimal 97, por tanto restandole ese valor nos queda 0 (que es la posición que le habíamos asignado en el array). De esta forma solo tienes que recorrer una vez la frase y otra el array, que es tiempo constante.
Al imprimir los valores solo debes deshacer el cambio, es decir, la posición 0 será la 'a', la posición 1 la 'b', etc e imprimiremos aquellas posiciones que sean distintas de 0.
Un saludo.