rsa_generate_private_key() function that was changed in version 5.4 to use the more common 65537 (RSA_F4) was introduced in key.c by this commit back in 2000, and already have the public exponent at 35. However, if you go back in time that function already existed in rsa.c before and the first revision from 1999 was already using 35 from the start, its creation part of a large refactoring effort to stop using gmp and to use OpenSSL's libcrypto functions instead.
Trying to see when 35 was first introduced, and found that in the 1.0 release of Tatu Ylönen's SSH the public exponent was generated by the following code (function
derive_rsa_keys() called from
rsa_generate_key() in rsa.c) which would have stumbled on 35 often, but not always.
/* Find a suitable e (the public exponent). */
mpz_mul_2exp(e, e, ebits);
mpz_sub_ui(e, e, 1); /* make lowest bit 1, and substract 2. */
/* Keep adding 2 until it is relatively prime to (p-1)(q-1). */
mpz_add_ui(e, e, 2);
mpz_gcd(&aux, e, &phi);
while (mpz_cmp_ui(&aux, 1) != 0);
That code stayed the same until ssh-1.2.12 which is the most recent OpenSSH ancestor in the original SSH line. In OSSH-1.2.16 (intermediate ancestor to OpenSSH) it also stayed the same, and afterwards it seems during the SSH import in the OpenBSD tree, the refactoring to use libcrypto instead of libgmp in 1999 happened immediately and introduced the fixed 35. If CVS is to be trusted it's Niels Provos that did the work (but likely in close communication with Markus Friedl and others), and as the commit message doesn't mention a reason only him should know for sure why he chose 35.
However, from my point of view, even if it wasn't the best choice for keygen performance (Peter Gutmann going as far as calling it cargo culting) it was the safe conservative choice, as with so many SSH keys in usage already with 35 as public exponent, there was quasi certainty this would not introduce any breakage.