We propose a variational approach for computing the macroscopic entanglement in a many-body mixed state, based on entanglement witness operators, and compute the entanglement of formation (EoF), a mixed-state generalization of the entanglement entropy, in single- and two-channel Kondo systems at finite temperature. The thermal suppression of the EoF obeys power-law scaling at low temperature. The scaling exponent is halved from the single- to the two-channel system, which is attributed, using a bosonization method, to the non-Fermi liquid behavior of a Majorana fermion, a "half" of a complex fermion, emerging in the two-channel system. Moreover, the EoF characterizes the size and power-law tail of the Kondo screening cloud of the single-channel system.