As the only nonlinear module, S-Box (substitution box) is widely used in stream cipher, hash function, and so on. However, there exist some weaknesses in existing S-Boxes, such as fixed point, reverse fixed point and short iteration period rings. Furthermore, the S-Boxes in AES and SM4.0 were fixed, which makes them vulnerable to attack. To address these weaknesses, first, a non-degenerate 2D chaotic map (2D-NDCM) with ergodicity in phase space was constructed. Second, based on 2D-NDCM, the seed S-Boxes with high nonlinearity were constructed in batches by affine transformation and Boolean function, and then three possible weaknesses were eliminated to obtain strong keyed S-Boxes. Statistical analysis demonstrated the effectiveness and practicability of the proposed S-Box batch generating algorithm.