No, it's not OK. You have a high resistance in the cabling, somewhere. If you have cleaned the battery terminal connections, and the connections at the starter relay, next is the battery negative cable where it attaches at the frame and the rear of the transmission. I use DeoxIT with a brass brush to make sure all surfaces are clean and good conductors. Make sure you feel the cable for unusual stiffness, or a 'crunchy' feeling when you flex it, which is a sign the cable is failing inside the insulation.