Includi l'header time.h e aggiungi questa riga prima della chiamata alla rand:

srand(time(NULL));

Il seed va inizializzato!