Só um detalhe: fgets lê os dados até encontrar uma quebra de linha ou ler a quantidade máxima de caracteres. Isso quer dizer que se tiver uma linha maior do que MAX_LINE_LEN, ele não lerá a linha toda.

Uma abordagem mais garantida é ir lendo os caracteres e guardando em um buffer, até encontrar a quebra de linha (ou o final do arquivo, que indicaria a última linha). Mas se o tamanho máximo for atingido antes disso, bastaria realocar para um tamanho maior. Eu me baseei neste código e adaptei para o seu caso.

Outro ponto é que não precisa ler o arquivo duas vezes (uma para ver a quantidade de linhas, outro para buscar a linha aleatória). Você pode ir lendo apenas uma vez, usando este algoritmo (que também adaptei para o seu caso). A ideia é que a cada linha você teste se 1 dividido pelo número da linha é maior que um determinado valor aleatório - mas para isso ele usa a função drand48, que retorna um float aleatório entre 0 e 1 (disponível apenas no Linux - para Windows, tem outras alternativas).

Enfim, ficou assim:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

char *choose_random_line(FILE *f) {
    srand48(time(NULL));
    int current_max = 256; // um tamanho inicial qualquer
    char *selected = malloc(current_max);
    char *current = malloc(current_max);
    selected[0] = '\0';

    int length = 0, line_number = 0;
    int ch = 0;
    while (ch != EOF) {
        ch = fgetc(f);
        if (length == current_max) { // atingiu o tamanho máximo, realocar mais memória
            current_max *= 2; // uma estratégia comum é dobrar o tamanho
            current = realloc(current, current_max);
            selected = realloc(selected, current_max);
            // pode incluir if (selected == NULL) para verificar se conseguiu realocar, etc
        }

        if (ch == '\n' || ch == EOF) { // terminou a linha ou o arquivo
            current[length] = '\0';
            if (drand48() < 1.0 / ++line_number) { // aleatoriamente pode selecionar esta linha
                strcpy(selected, current);
            }
            length = 0;
            continue;
        }

        current[length++] = ch;
    }
    free(current);

    return selected;
}

int main(void) {
    FILE *f = fopen("texto.txt", "r");
    if (f == NULL) {
        fprintf(stderr, "Error when trying to read file.\n");
        return 1;
    }
    char *random_line = choose_random_line(f);
    printf("Linha aleatória: %s\n", random_line);
    free(random_line);
    fclose(f);
    return 0;
}