I suppose they're kept encrypted as not to do so would be the equivalent as saving plaintext passwords. I heard most of them keep a percentage of the funds in cold storage, but then isn't it inconvenient for the users in case a lot of them want to withdraw funds? how to manage those conflicting interests? Also how is the actual key being generated? where does the source of randomness come from?
To support timely settlement services outside an exchange's platform, around 1/12 to 1/16 value of an exchange's cryptocurrency value will probably need to be placed in hot storage. The rest will be in cold storage. Conceptually, fractional hot to cold storage ratios are analogous to fractional reserve banking and PBX trunk sizing.
The cybersecurity ante for the "state-of-the-practice" for exchanges and payment processors business as usual needs to be upped. Don't even think about just a bunch of keys (JBOK) management. Hierarchical Deterministic (HD) technology is really the only viable approach to minimize key management complexity that can eat you alive. Insider threats will be one of the largest attack surfaces for exchanges. Employee background checks will be inadequate. Multisig support is critical to ensure internal separation of duties to prevent conflicts of interests.
For concise Dash examples about how to apply BIP 32/38/44 to altcoin key synthesis, and address generation (for both public and private extended keys) see answer URLs reference by BIP 38 Implementions for Altcoins?, in particular see this recent Wiki Posting.
Supporting multisig signature capability will be critical for minimizing the exposure of an exchange's cold and hot wallet assets. Suspect the libbitcoin multisig transaction composition interface will work for numerous altcoins, since I've tested it for BTC and TEST coins a few months back. However, still need to validate that bx multisig interface works with the newly supported altcoin "version" interface. Extra validation work is required to ascertain which altcoins bx can successfully create version 1 text formatted multisignature transactions, and which altcoin network consensus mechanisms no kidding truly support multisig blockchain capabilities.
Multisig technologies alone do not prevent out-of-band multisig workflow spoofing attacks... ask BitP++. Suspect exchanges and payment services practicing "due diligence" and "due care" will eventually learn they must also deploy expensive to design/deploy/sustain controlled interface CDS technologies.
Most large services use a split wallet system where the money is divided into a small "hot" wallet which does day to day activity, and a "cold" wallet which stores the bulk of the money offline and behind physical security. A cold wallet can be both physically protected, and have divided spending responsibility between multiple parties to avoid internal theft. This has the advantage of minimizing losses if the hot wallet is compromised, but will delay extremely high amounts of rates of withdraws as there is a human element (possibly several) in the chain. There is a trade off with the amount of money you have in which side of the split, more in the hot wallet has a higher risk of internet directed thefts, but higher convenience.
Most companies don't disclose how they make their keys, but one can assume they are hardened BIP32 child keys, or individually produced Bitcoin addresses made on a dedicated system. Usually in this sort of setup everybody will use the standard RNG
/dev/urandom which is a cryptographically secure random number generator designed explicitly for this task.