Here is the simple solution:
You should not use Label at all, because it is redundant; the check box has its own text. Do something like this:
<input type="checkbox" id="chkId1" accesskey="A">This is option <u>A</u></input><br/>
<input type="checkbox" id="chkId2" accesskey="B">This is option <u>B</u></input>
This way, you will create accelerator keys for each control, according to underlined characters. Remember that in Mozilla, they are accessed via Alt+Shift+key, but on some other browsers via Alt+key.
As to the slow operation, this is not true. You could screw up your performance somewhere else; those controls themselves work just fine, and very fast.