I can't make this circuit work as expected and generate random events every time I turn on the power. I have checked NAND gates (IC3B, IC3C) and they generating clock signal with no problem. The only way to "kick" the circuit to start working, is to short D5 IC20 with the power pin. I have added a simple RC circuit generating a short pulse to the D5 input and it helps, but also, not every time. Another problem is that the signal at the LFSR output is different than the original one - it contains spikes caused by C1/47n capacitor. I would appreciate your advice.
The problem with LFSRs is that you need a non-zero initial value. If the value of all registers is zero, then the next state will always be zero. This is why you need to "kick" the circuit into life as you put it.
Fortunately you have almost everything you need to do this, with just a minor tweak. The 4171 has a reset signal. This will force all register values to zero when asserted. But wait, we don't want all zeros!
So we tweak the circuit such that resetting a given register value to 0 will actually force a 1 into the chain. To make one of the registers 1 when reset, we first need to add a NOT gate to the output - the 0 reset value will now appear as a 1 in the chain.
However we have now changed the characteristic of the chain, because there is an inverter in it. But we can compensate for that. We now know that this particular register uses a 0 to represent 1, so when feeding a 1 into its D pin, we need to invert it to match. The two NOT gates in the data part feedback chain cancel out. But there is still only one NOT gate in the reset part so we still get our non-zero starting value.
Now at power on, you just need to hold the reset pin low momentarily - adding an R-C circuit to the pin will accomplish. You may need to also add a schmitt trigger between the R-C and the !RESET! pin depending on how it reacts to slow rising signals.
You should also remove R69 and C51 as these are no longer necessary and will not do you any good.
As you are using a 4011 in the design already, you can get the two inverters you need without adding an extra IC. The 4011 is a quad 2-in NAND gate, and you appear to only be using two of those gates in the design at the moment. A NAND gate can be converted into a NOT gate by tying the inputs together, so IC3 can provide you with the two NOT gates for your chain.
Furthermore as @JonathanS notes in the comments, the spikes you get are caused by the delay introduced by the R-C circuit you were contemplating adding to the input of the XOR. This delay causes a glitch in the output.
Even in the proposed modified version in this answer, you can ensure a glitch free output by taking the output from Q0 of IC20 (after the not gate in my tweaked example) rather than from the XOR gate. The clocked register will filter out any glitches in the output stream which are narrower than the clock period.