Faits :
A.
Par ordonnance du 4 novembre 2020, le Tribunal de l'application des peines et mesures du canton du Valais a constaté l'échec de la mesure thérapeutique institutionnelle au sens de l'<ref-law> ordonnée contre A._ par jugement du Tribunal cantonal du 26 novembre 2013. Il a levé cette mesure (<ref-law>) et a ordonné, en lieu et place, l'internement (<ref-law>). Il a par ailleurs dit que, pour autant qu'elle n'ait pas encore été exécutée (<ref-law>), la peine privative de liberté de 6 ans, sous déduction de la détention subie à Genève du 8 décembre 2008 au 10 décembre 2010 et de la détention avant jugement subie à compter du 6 mai 2011, devra être exécutée avant l'internement (<ref-law>). Il a mis les frais par 21'420 fr. 35 à la charge de l'État du Valais au titre de l'assistance judiciaire, sauf l'indemnité de défenseur d'office que A._ devra rembourser à l'État du Valais, de même qu'il devra rembourser à son défenseur d'office la différence entre son indemnité en tant que défenseur désigné et les honoraires qu'il aurait touchés en tant que défenseur privé.
B.
Par ordonnance du 29 janvier 2021, la Chambre pénale du Tribunal cantonal du Valais a rejeté le recours formé par A._.
En résumé, il en ressort les éléments suivants.
B.a. Par jugement du 26 novembre 2013 du Tribunal cantonal du canton du Valais, A._ a été reconnu coupable de viols avec cruauté, de tentative de viol, de tentative de viol avec cruauté, de contraintes sexuelles avec cruauté, de tentative de contrainte sexuelle avec cruauté, de séquestration et de voies de fait. Il a été condamné à une peine privative de liberté de six ans, sous déduction de la détention avant jugement subie du 8 décembre 2008 au 10 décembre 2010 et dès le 6 mai 2011, ainsi qu'à une amende de 200 fr., la peine privative de liberté de substitution en cas de non-paiement fautif de l'amende étant fixée à cinq jours. Le sursis partiel de sept mois accordé à la peine privative de liberté de treize mois prononcée le 22 mars 2010 par le Tribunal cantonal du canton du Valais a été révoqué. En outre, A._ a été soumis à une mesure thérapeutique institutionnelle en milieu fermé (art. 59 al. 1 et 3 CP) pour le traitement de ses troubles mentaux.
Par arrêt du 13 août 2014 (6B_84/2014), le Tribunal fédéral a rejeté le recours formé par A._ contre le jugement cantonal du 26 novembre 2013.
A._ a été détenu du 7 mai 2011 au 20 septembre 2012 à la prison S._, du 20 septembre 2012 au 21 mars 2014 à la prison T._, du 21 mars 2014 au 13 juillet 2015 à la prison U._, à V._, du 13 juillet 2015 au 5 décembre 2016 à la prison S._, du 5 décembre 2016 au 8 novembre 2018 à l'établissement pénitentiaire fermé W._ à X._, du 8 novembre 2018 au 22 mars 2019 à la prison S._ et depuis le 22 mars 2019 jusqu'à ce jour à Y._.
B.b. Lors de l'examen annuel au sens de l'<ref-law> de la mesure thérapeutique institutionnelle, le Tribunal de l'application des peines et mesures (ci-après : TAPEM) a, par décisions du 14 décembre 2015, respectivement du 19 janvier 2017 et du 30 octobre 2018, prononcé le maintien de la mesure imposée à A._, jusqu'au 26 novembre 2023.
Par ordonnance du 20 avril 2018, le TAPEM a considéré que le maintien en détention de A._ dans un établissement carcéral entre le 23 juin 2015 et le 5 décembre 2016 avait contrevenu à l'art. 5 par. 1 let. e CEDH.
B.c. Dans le cadre de l'examen annuel de la mesure, l'Office des sanctions et des mesures d'accompagnement (ci-après : l'OSAMA) a saisi le TAPEM, le 13 décembre 2018. Parmi les documents annexés à cette requête figurait notamment l'extrait du procès-verbal de la séance du 10 décembre 2018 de la Commission pour l'examen de la dangerosité du canton du Valais, laquelle a recommandé de refuser la libération et la levée de la mesure (<ref-law>) et d'ordonner la mise en oeuvre d'une expertise indépendante (<ref-law>).
Le 21 juin 2019, la Dresse B._ et le Dr C._, qui exercent tous deux au sein de l'établissement W._, à X._, ont été interrogés par le juge du TAPEM. Le 19 juillet 2019, D._, responsable de l'exécution des mesures à W._ a été entendu.
B.d. Par décision du 5 août 2019, le juge du TAPEM a mandaté le Dr E._, du Centre Z._, pour réaliser l'expertise psychiatrique de A._. L'expert a déposé son rapport le 1er novembre 2019. Une séance relative à un complément d'expertise a été organisée le 27 février 2020 en présence de l'expert. Ce dernier a encore rédigé un complément d'expertise le 6 mai 2020.
Les parties ont finalement comparu devant le TAPEM, composé des trois juges, le 22 septembre 2020. Par courrier du même jour, l'OSAMA a conclu à ce que le TAPEM prononce l'internement de A._.
C.
A._ forme un recours en matière pénale au Tribunal fédéral contre l'ordonnance du 29 janvier 2021. Il conclut, principalement à son annulation en ce sens que la mesure thérapeutique institutionnelle est maintenue jusqu'au 26 novembre 2023. Subsidiairement, il conclut à l'annulation de l'ordonnance et au renvoi de la cause à la cour cantonale pour nouvelle ordonnance dans le sens des considérants. Il requiert la désignation de Me Yaël Hayat en qualité de défenseur d'office, respectivement le bénéfice de l'assistance judiciaire et la dispense de l'avance et du paiement des frais judiciaires.
Invités à se déterminer sur le recours, l'office des sanctions et des mesures d'accompagnement du canton du Valais a conclu à son rejet et la cour cantonale n'a pas formulé d'observations se référant aux considérants de son ordonnance.

Considérant en droit :
1.
Le recourant reproche à la cour cantonale d'avoir apprécié les preuves et établi les faits de manière arbitraire et invoque une violation des art. 56, 59, 62c et 64 CP.
1.1. Le Tribunal fédéral n'est pas une autorité d'appel, auprès de laquelle les faits pourraient être rediscutés librement. Il est lié par les constatations de faits de la décision entreprise (<ref-law>), à moins qu'elles n'aient été établies en violation du droit ou de manière manifestement inexacte au sens des art. 97 al. 1 et 105 al. 2 LTF, à savoir, pour l'essentiel, de façon arbitraire au sens de l'art. 9 Cst. Une décision n'est pas arbitraire du seul fait qu'elle apparaît discutable ou même critiquable; il faut qu'elle soit manifestement insoutenable et cela non seulement dans sa motivation mais aussi dans son résultat (<ref-ruling> consid. 1.1; <ref-ruling> consid. 1.1; sur la notion d'arbitraire v. <ref-ruling> consid. 2.3.1). Le Tribunal fédéral n'entre en matière sur les moyens fondés sur la violation de droits fondamentaux, dont l'interdiction de l'arbitraire, que s'ils ont été invoqués et motivés de manière précise (<ref-law>; ATF <ref-ruling> consid. 1.1). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 1.1).
1.2. Aux termes de l'<ref-law>, lorsque l'auteur souffre d'un grave trouble mental, le juge peut ordonner un traitement institutionnel lorsque celui-ci a commis un crime ou un délit en relation avec ce trouble (let. a) et qu'il est à prévoir que cette mesure le détournera de nouvelles infractions en relation avec ce trouble (let. b). Selon la jurisprudence, la condition posée par l'<ref-law> - qu'il soit à prévoir que la mesure détournera l'intéressé de nouvelles infractions en relation avec son trouble - est réalisée lorsque, au moment de la décision, il est suffisamment vraisemblable qu'un traitement institutionnel entraînera dans les cinq ans de sa durée normale une réduction nette du risque de récidive (<ref-ruling> consid. 3.2.4; <ref-ruling> consid. 3.4.1).
Conformément à l'<ref-law>, une mesure dont les conditions ne sont plus remplies doit être levée. Comme son prononcé suppose qu'elle soit propre à détourner l'auteur de la commission de nouvelles infractions en relation avec son grave trouble mental (cf. <ref-law>), une mesure thérapeutique institutionnelle ne peut dès lors être maintenue que si elle conserve une chance de succès, ainsi que le prévoit d'ailleurs l'<ref-law>. Selon cette dernière disposition, la mesure thérapeutique institutionnelle doit être levée si son exécution paraît vouée à l'échec. Il en va ainsi lorsque l'auteur n'est pas - ou plus - soignable ou que le traitement n'est plus apte à prévenir la commission de nouvelles infractions. L'échec de la mesure peut résulter de l'insuffisance de possibilités thérapeutiques, du manque de respect des avis ou recommandations des thérapeutes ou du refus d'un traitement. Le traitement n'est voué à l'échec que s'il est définitivement inopérant; une simple crise de l'intéressé ne suffit pas. De manière générale, la levée d'une mesure en raison de son échec doit être admise de manière restrictive (<ref-ruling> consid. 2.2; <ref-ruling> consid. 2.3; arrêts cf. 6B_684/2020 du 21 avril 2021 consid.1.2.3, 6B_1143/2019 du 31 octobre 2019 consid. 1.1). L'appréciation du pronostic légal et la question du bénéfice thérapeutique concernent des questions de faits que le Tribunal fédéral ne revoit que sous l'angle de l'arbitraire (arrêt 6B_82/2021 du 1er avril 2021 consid 4.2.3 destiné à la publication).
1.3. En substance, la cour cantonale a estimé que les premiers juges pouvaient considérer que la mesure thérapeutique institutionnelle dont bénéficiait le recourant était vouée à l'échec et que les conditions de l'internement étaient réalisées. A cet égard, elle a retenu qu'il ressortait de l'expertise du 1er novembre 2019 du Dr E._ que le recourant souffrait d'un trouble mixte de la personnalité paranoïaque et dyssociale, d'une accentuation de traits de personnalité narcissique, ainsi que d'antécédents de troubles mentaux et de troubles du comportement liés à l'utilisation d'alcool, utilisation nocive pour la santé. La cour cantonale a retenu, en citant cette même expertise, que l'expert était parvenu à la conclusion, s'agissant du résultat de la mesure thérapeutique institutionnelle, que celle-ci s'était soldée par un échec, et que selon lui la prise en charge psychiatrique des personnes souffrant d'un trouble de la personnalité paranoïaque était longue, difficile et peu probante. Celle-ci consistait surtout à essayer d'établir une alliance minimale avec un patient qui ne demande pas de soins. La cour cantonale a également retenu que l'expert avait souligné que sur le plan médicamenteux, les neuroleptiques étaient peu efficaces et que le recourant ne semblait laisser aucune brèche à une relation de confiance.
La cour cantonale a retenu que le rapport d'évaluation criminologique du 12 mars 2020 relativisait les conclusions de l'expertise du 1er novembre 2019 et du rapport du 21 février 2020. Il en ressortait que plusieurs études criminologiques relevaient qu'une intervention par le biais de programmes de type cognitivo-comportemental pouvait être prometteuse en matière de désistance chez les délinquants présentant des caractéristiques psychopathiques; et, qu'une réflexion quant à l'intégration du recourant au sein d'un groupe pour auteurs d'infractions à caractère sexuel pourrait être envisagée. Cependant, en s'appuyant sur le complément d'expertise du 6 mai 2020 du Dr E._ qui se prononce sur ce rapport du 12 mars 2020, la cour cantonale a retenu que ces approches thérapeutiques existaient uniquement d'un point de vue théorique et qu'elles ne tenaient pas suffisamment compte des non-avancements thérapeutiques obtenus jusqu'alors par le recourant. En outre, la cour cantonale a retenu que s'agissant d'éventuels autres établissements, qui seraient à même de proposer des approches différentes que celles offertes au sein de Y._, il n'était pas suffisant que le recourant constate leur existence. Selon elle, non seulement il aurait fallu que ceux-ci - dont l'emplacement restait inconnu - soient disposés à accueillir le recourant, mais aussi que le recourant démontre une réelle volonté d'être prêt à s'impliquer dans un quelconque traitement, ce dont elle doutait au vu des pièces du dossier.
La cour cantonale a retenu que la détention illicite (cf. supra let. B.b) du recourant n'avait pas eu de conséquence sur les capacités de celui-ci à se soumettre au traitement thérapeutique. A cet égard, elle a toutefois retenu que ce n'était qu'à partir du transfert du recourant à W._ que la mesure thérapeutique institutionnelle avait pu débuter, le milieu carcéral n'étant pas adapté à prodiguer les soins adaptés à l'état de santé de l'intéressé. Elle a également admis qu'en théorie, si le recourant avait été placé dans cet établissement dans de meilleurs délais, il aurait pu débuter plus tôt son traitement. Elle a toutefois relativisé ces éléments en relevant que, de toute manière, le recourant ne s'était pas montré disposé à entamer une véritable introspection et une remise en question et que l'expert avait déclaré n'être pas en mesure de dire quelles avaient été les répercussions de la détention illicite sur le psychisme du recourant. De plus, elle a souligné que le recourant n'avait jamais précisé quelles auraient été les conséquences d'un placement plus rapide à W._ sur ses capacités à se soumettre au traitement.
S'agissant de la durée effective de la mesure thérapeutique dont avait bénéficié le recourant, la cour cantonale a retenu qu'indépendamment de cette durée - que celle-ci ait duré plus de cinq ans ou trois ans seulement - le recourant s'était toujours montré inaccessible au traitement et qu'ainsi c'était la motivation du recourant à s'investir dans un traitement thérapeutique qui faisait défaut. Par ailleurs, elle a souligné que le droit ne prévoyait pas de durée minimale de traitement.
A propos du complément d'expertise du 6 mai 2020, la cour cantonale a retenu que le Dr E._ avait précisé que la seule question qui lui semblait encore restée ouverte était celle de la durée nécessaire pour prononcer l'échec du traitement. Que selon lui, "[o]n pourrait, éventuellement considérer que le temps passé depuis le début de la thérapie à W._, suivi de celle qui [était] actuellement en cours avec le Dr F._ [était] trop court si l'on [tenait] compte des puissants mécanismes de défense (clivage, déni) présents chez l'expertisé", mais que "c'[était] toutefois l'intensité et la rigidité de ces mêmes mécanismes de défense qui laisse[aient] peu de place au changement et à la remise en question".
Au final, en se fondant sur les rapports d'évaluation criminologique, l'expertise psychiatrique et son complément, la cour cantonale a retenu que le recourant n'avait guère évolué dans son travail thérapeutique, puisqu'il se positionnait toujours dans le déni et le refus de se remettre en question. Face à ce manque de motivation, la cour cantonale a conclu qu'elle ne percevait guère de quelle manière la mesure thérapeutique institutionnelle pourrait encore atteindre son but.
En ce qui concerne le risque de récidive, la cour cantonale a retenu que l'expert l'avait qualifié d'élevé pour des actes de violence, y compris pour des actes de violence sexuelle et au vu de ce risque élevé, l'expert avait préconisé un internement au sens de l'<ref-law>.
1.4. Le recourant débute ses écritures par une présentation personnelle des faits. Dans la mesure où il s'écarte des faits retenus par la cour cantonale sans démontrer que ceux-ci auraient été établis de manière arbitraire, son exposé est appellatoire, partant irrecevable.
1.5. Le recourant remet en cause l'appréciation de la cour cantonale s'agissant de l'absence de perspectives thérapeutiques invoquant l'existence d'autres traitements thérapeutiques. Le recourant soutient qu'une lecture combinée du rapport d'évaluation criminologique du 12 mars 2020 avec le complément d'expertise du 6 mai 2020 aurait dû conduire la cour cantonale à ne pas exclure l'existence d'autres perspectives thérapeutiques. Il ressortirait de ce rapport qu'une intervention par le biais de programmes de type cognitivo-comportemental serait indiquée et que l'intégration du recourant au sein d'un groupe pour auteurs d'infractions à caractère sexuel pourrait être envisagée. Le recourant prétend que ce constat serait renforcé par le complément d'expertise du 6 mai 2020, qui n'aurait pas été pris en compte par la cour cantonale. En tant que l'argumentation du recourant consiste uniquement à opposer sa propre appréciation des moyens de preuve à celle de la cour cantonale, elle est purement appellatoire. Au demeurant, contrairement à ce que prétend le recourant, la cour cantonale a minutieusement examiné le complément d'expertise du 6 mai 2020, dans lequel l'expert se prononce spécifiquement sur le contenu du rapport d'évaluation du 12 mars 2020. C'est d'ailleurs en se fondant sur ce complément d'expertise que la cour cantonale a écarté l'existence d'autres traitements thérapeutiques pertinents, dès lors que selon l'expert ces propositions thérapeutiques étaient uniquement théoriques et qu'elles ne tenaient pas compte des non-avancements thérapeutiques obtenus jusque-là par le recourant, ni d'ailleurs des traits paranoïdes du recourant. Au vu de ce qui précède, la cour cantonale pouvait, sans verser dans l'arbitraire, considérer que les programmes en question ne permettaient pas encore de retenir qu'il existait d'autres alternatives thérapeutiques.
1.6. Le recourant soutient que d'un point de vue temporel, la cour cantonale aurait conclu de manière prématurée à l'échec de la mesure thérapeutique institutionnelle. Il argue que l'expert, le Dr E._, aurait lui-même, par le biais de son complément d'expertise daté du 6 mai 2020 relativisé ses propos s'agissant de l'échec de la mesure. Il aurait laissé expressément la question de la durée nécessaire pour prononcer l'échec de la mesure ouverte. Le recourant estime que la condition relative à l'échec définitif de la mesure ne serait pas réalisée et que la cour cantonale aurait ainsi violé le droit en levant cette mesure et en prononçant l'internement qui devrait demeurer l' ultima ratio.
En l'espèce, dans son ordonnance, la cour cantonale a éludé la problématique de la durée de la mesure et du caractère éventuellement prématuré du constat d'échec en faisant valoir que dans tous les cas, le recourant était inaccessible au traitement. Cela étant, elle n'a pas constaté que celui-ci refusait le traitement. Au contraire, elle a retenu qu'il se rendait régulièrement aux entretiens avec son thérapeute. A cet égard, il ressort également du complément d'expertise que malgré les grandes difficultés du recourant à avancer dans le travail thérapeutique, son investissement était qualifié de bon (cf. complément d'expertise du 6 mai 2020 p. 15, pièce 1546 dossier cantonal; <ref-law>). Ainsi, on ne peut pas dénier qu'il existe chez le recourant, à tout le moins, un minimum suffisant de volonté de coopération dans le cadre de la mesure (cf. arrêt 6B_1223/2019 du 27 mars 2020, consid. 7.2.2). Cet élément est d'autant plus important que l'expert, comme l'a retenu la cour cantonale, a souligné que la prise en charge psychiatrique des personnes souffrant d'un trouble de la personnalité paranoïaque était particulièrement longue et consistait surtout à essayer d'établir une alliance minimale avec le patient. Dès lors que le caractère long d'une telle prise en charge a été retenu, l'aspect temporel de la mesure apparaît d'autant plus important pour pouvoir constater un échec définitif. A cet égard, il faut souligner que la cour cantonale a retenu que ce n'était qu'à partir du transfert du recourant à W._ que la mesure thérapeutique institutionnelle avait pu débuter, le milieu carcéral n'étant pas adapté à prodiguer les soins adaptés à l'état de santé de l'intéressé. D'ailleurs, le parcours carcéral particulièrement décousu du recourant ressort clairement de l'ordonnance attaquée. Ainsi, il convient de déterminer si, en l'espèce, le constat d'échec était définitif.
Dans son complément d'expertise du 6 mai 2020, le Dr E._ qui était appelé à se prononcer sur le maintien de ses précédentes conclusions a répondu que la seule question qui lui semblait restée encore ouverte était celle de la durée nécessaire pour prononcer l'échec du traitement. Selon lui, le temps passé depuis le début de la thérapie à W._, suivi de celle qui était actuellement en cours avec le Dr F._ était trop court, si l'on tenait compte des puissants mécanismes de défense présents chez le recourant. Il a relevé que c'était toutefois l'intensité et la rigidité de ces mêmes mécanismes de défense qui laissaient peu de place au changement et à la remise en question. Finalement, il a conclu par le constat qu'"actuellement" la mesure était un échec et que peu ou pas de changements semblaient "aujourd'hui" possibles (cf. complément d'expertise du 6 mai 2020, p. 16; <ref-law>). Sur la base de ces affirmations, il ressort qu'il était trop tôt pour se déterminer sur le caractère définitif de l'échec de la mesure. En effet, l'expert a nuancé expressément ses précédentes conclusions, en admettant que la question de la durée nécessaire pour se prononcer sur un tel échec restait encore ouverte. Il a admis que dans le cas du recourant, qui était doté de puissants mécanismes de défense, la durée du traitement semblait trop courte. Il n'a pas exclu toutes chances d'évolutions, même si celles-ci restaient minces. Finalement, dans sa conclusion, en utilisant les mots "actuellement" et "aujourd'hui", l'expert a indiqué que son constat était relatif à la situation présente, se gardant bien de se prononcer de manière irrémédiable sur l'avenir du traitement. Or, la jurisprudence exige justement que le constat d'échec soit définitif et que l'admission d'une levée de mesure thérapeutique institutionnelle sur cette base soit restrictive. Ainsi, au vu de la question soulevée par l'expert, de son constat limité à la situation actuelle et au fait qu'il n'exclut pas totalement des possibilités de changement, il n'était pas possible de dire que l'échec de la mesure était définitif.
Au regard de ce qui précède, la cour cantonale s'est prononcée de manière prématurée sur le constat de l'échec de la mesure thérapeutique institutionnelle, dès lors qu'il subsistait un doute sur son caractère définitif. La cour cantonale a ainsi violé le droit fédéral en levant la mesure en application de l'<ref-law> et en prononçant l'internement du recourant (<ref-law>).
2.
Le recours doit être admis, l'ordonnance attaquée doit être annulée, sans qu'il soit nécessaire d'examiner les autres griefs soulevés. La cause sera renvoyée à la cour cantonale, afin qu'elle ordonne la poursuite de la mesure thérapeutique institutionnelle et qu'elle statue sur les frais et indemnités.
3.
Le recourant, qui obtient gain de cause, n'a pas à supporter de frais judiciaires (<ref-law>). Il a droit à des pleins dépens à la charge du canton du Valais, ce qui rend sans objet sa demande d'assistance judiciaire (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'ordonnance entreprise est annulée et la cause est renvoyée à la cour cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton du Valais versera au mandataire du recourant une indemnité de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Chambre pénale.
Lausanne, le 14 juillet 2021
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
La Présidente : Jacquemoud-Rossari
La Greffière : Meriboute