Two things. First of all, wouldn't brute-forcing the key generation exhaust the entropy available in /dev/random and force the use of less random bits from /dev/urandom?

Once properly seeded, /dev/urandom is good enough. The main issue with it is initial seeding and not using up entropy.

Also, don't the public/private keys need to be based on prime numbers, not just random numbers? The strength of RSA is the assumption that factorization of large _prime_ numbers is mathematically a hard problem to solve.

CJDNS doesn't use RSA. It uses elliptic curve crypto, specifically Curve25519, where a private key is just a random number. No need for being a prime.