Ti consiglio queste modifiche

codice:
   /* inizializzazione file */
   ...
   fprintf(fp, "%06d \n", i);  // Determina un numero fisso di cifre
   ...

   /* aggiunta nuova stringa e aggiornamento contatore stringhe presenti nel file */
   fp=fopen("prova.txt", "r+");  // File in r+
   fscanf(fp, "%d", &cont);
   rewind(fp);
   fprintf(fp, "%06d", ++cont);
   fseek(fp, 0L, SEEK_END);
   fputs(stringa, fp);
   fclose(fp);